21
Here's an optimal procedure that lets you find out the status of every person after exactly
questions:
Reasoning:
Proof of optimality:
6
Firstly, the bottles:
Now let's compare prices of the two different types of alcohol purchases:
In total you need 32 times 500 ml, which is 66⅔ times 240 ml or 200 times 80 ml. Firstly, buy
After all that, you still have one coupon in hand and 1600 ml left to get (that's 6⅔ times 240 ml or 20 times 80 ml). Now buy
So the overall expenditure is
4
A better upper bound is
Solution:
P.S.
3
You can solve the problem via integer linear programming as follows. There are only nine useful purchases to consider, and I enumerated them by hand:
2 80mL bottles: cost \$20
1 240mL bottle: cost \$36
1 PET bottle: cost \$5
3 240mL bottles, 1 coupon: cost \$52
1 240mL bottle, 2 80mL bottles, 1 coupon: cost \$41
1 240mL bottle, 9 PET bottles, 1 coupon: ...
3
A naive upper bound is
EDIT:
Only top voted, non community-wiki answers of a minimum length are eligible
