7
$\begingroup$

You are the principal of a primary school in HK. Schools are resuming soon, and you have to ensure that your school have enough alcohol. Each of the 30 classrooms should have a bottle containing 500mL alcohol, and the staff room should have 2 bottles of 500mL of alcohol.

You searched on the web and found the following site, which the alcohol sold on the site is good quality:

Alcohol 80 mL: $20 (Buy 1 get 1 free)

Alcohol 240 mL: $36 (Buy 2 get 1 free)

PET bottles for alcohol with 500mL capacity: $5

COVID-19 offer: For each purchase of Alcohol or PET bottles at least \$80(before discount), you get a \$20 coupon for your next purchase!

You have no coupons or membership cards now. How much do you need to spend at least to buy enough Alcohol and PET bottles?

Full solutions and no computers.

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ What's the legal drinking age in HK? $\endgroup$
    – msh210
    May 31, 2020 at 15:13
  • 3
    $\begingroup$ @msh210 18. BTW, the alcohol is for killing germs, not for drinking! $\endgroup$
    – Culver Kwan
    Jun 1, 2020 at 1:05

2 Answers 2

Reset to default
6
$\begingroup$

Firstly, the bottles:

you need to buy 32 PET bottles costing \$5 each, and there's no way around that. So you can spend \$160 on those bottles right away, earning two \$20 coupons in the process, which means spending just \$140 and having one coupon in hand.

Now let's compare prices of the two different types of alcohol purchases:

  • At first glance, it's clear that the 240 ml bottle offers better value for money, since the amount is three times as much as the 80 ml bottle but a lot less than three times the price. But with the extra "buy 1/2 get 1 free" offers, things become more complicated ...

  • If you buy 6 of the 240 ml bottles (should be a multiple of 2 and 3), then you pay for 4 of them, so you spend \$144. To get the same amount of alcohol from 80 ml bottles, you need to pay 18 of those and pay for 9, so you spend \$180. But with the extra coupon offer, things become even more complicated ...

  • If you buy 12 of the 240 ml bottles (should be a multiple of 3 and 4), then you spend \$288 and get four \$20 coupons, which is equivalent to spending \$208. If you buy 36 of the 80 ml bottles for the same amount of alcohol, you spend \$360 and get nine \$20 coupons, which is equivalent to spending \$180. So in the end it's worth buying the 80 ml bottles for bulk purchases.

In total you need 32 times 500 ml, which is 66⅔ times 240 ml or 200 times 80 ml. Firstly, buy

180 of the 80 ml bottles (an exact multiple of the quantity of alcohol considered above), spending 5(\$180) = \$900 assuming the exact number of coupons are used (we can use one even on the first purchase, since we already have one left over from buying PET bottles).

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

20 more of the 80 ml bottles, in five purchases, spending 5(\$20) = \$100 by using all coupons, and again having one left over at the end.

So the overall expenditure is

\$140 + \$900 + \$100 = \$1140, and you also have one \$20 coupon left at the end (effective expenditure of \$1120, assuming you ever use that website again).

Improve this answer
$\endgroup$
8
  • $\begingroup$ buying the bottles greedily to get two coupons was my initial thought as well. But instead of 3 240 mL bottles of alcohol, you could buy 2 240 mL bottles of alcohol and 2 bottles. You can do this 16 times, then buy the remaining 34 240 mL bottles to get 10 more coupons. Wouldn't that net you 26 coupons for these items, where your current method nets only 24? $\endgroup$
    – Jeremy Dover
    May 31, 2020 at 12:50
  • $\begingroup$ @JeremyDover I think coupons are actually maximised by buying only 80 ml bottles, since then you can make it so all your purchases are exactly \$80. Have edited my answer. $\endgroup$
    – Rand al'Thor
    May 31, 2020 at 12:54
  • $\begingroup$ Agree. Nice solution! I wonder if there is a general approach involving linear programming. The batching for coupons is certainly a complication, but maybe you just run a series: buying in 10 batches (or some other reasonable starting point), buying in 11 batches, etc. $\endgroup$
    – Jeremy Dover
    May 31, 2020 at 13:14
  • $\begingroup$ 36 of the 80mL will cost $360 and yield 4 coupons (not 9 coupons) $\endgroup$
    – RobPratt
    May 31, 2020 at 16:10
  • 1
    $\begingroup$ OK, under that interpretation, your solution is optimal. $\endgroup$
    – RobPratt
    May 31, 2020 at 16:46
3
$\begingroup$

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:

  1. 2 80mL bottles: cost \$20
  2. 1 240mL bottle: cost \$36
  3. 1 PET bottle: cost \$5
  4. 3 240mL bottles, 1 coupon: cost \$52
  5. 1 240mL bottle, 2 80mL bottles, 1 coupon: cost \$41
  6. 1 240mL bottle, 9 PET bottles, 1 coupon: cost \$61
  7. 4 80mL bottles, 1 coupon: cost \$20
  8. 2 80mL bottles, 8 PET bottles, 1 coupon: cost \$40
  9. 16 PET bottles, 1 coupon: cost \$60

Let nonnegative integer decision variable $x_j$ represent the number of times purchase $j$ is made. The problem is to minimize $$20x_1 + 36x_2 + 5x_3 + 52x_4 + 41x_5 + 61x_6 + 20x_7 + 40x_8 + 60x_9$$ subject to \begin{align} 160x_1 + 240x_2 + 720x_4 + 400x_5 + 240x_6 + 320x_7 + 160x_8 &\ge 16000 \tag1 \\ x_3 + x_5 + 9x_6 + 8x_8 + 16x_9 &\ge 32 \tag2 \\ 20x_1 + 36x_2 + 5x_3 &\ge 20 \tag3 \end{align} Constraint $(1)$ enforces the alcohol demand. Constraint $(2)$ enforces the PET bottle demand. Constraint $(3)$ makes sure that at least \$20 of purchases do not generate a coupon.

In principle, you can solve this without a computer, but I didn't. :)

An optimal solution, with total cost

\$1140, is $x_1=1,x_7=50,x_9=2$, with all other $x_j=0$. This solution oversatisfies the alcohol demand by 160mL.

If you instead replace constraint $(3)$ with $$x_1 + x_2 + x_3 \ge 1 \tag4,$$ which means that at least one purchase must not generate a coupon, the resulting optimal solution, with total cost

\$1125, is $x_3=1,x_7=50,x_9=2$, with all other $x_j=0$. This solution oversatisfies the PET bottle demand by 1. Good luck getting the web site to honor a \$20 coupon for a \$5 purchase and give you a \$15 credit.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I don't think your final answer works: you can't buy everything with coupons except for one single PET bottle, because that one couponless purchase isn't \$80. I guess your last constraint needs to be that at least one purchase of \$80 or more must not generate a coupon. $\endgroup$
    – Rand al'Thor
    May 31, 2020 at 19:23
  • $\begingroup$ For each of the purchases besides that single PET bottle, you generate a coupon that you use for the next purchase. We just need to avoid the situation where all purchases use a coupon because then there can be no first purchase. $\endgroup$
    – RobPratt
    May 31, 2020 at 19:32
  • $\begingroup$ But which is the first purchase in your model? It seems that all purchases use a coupon except that single PET bottle which isn't enough to generate a coupon by itself. $\endgroup$
    – Rand al'Thor
    May 31, 2020 at 19:35
  • $\begingroup$ Any of them can be first, as long as the PET bottle is last. The accounting is a little creative here to avoid a time index that would unnecessarily inflate the size of the optimization model. The "cost" of a purchase includes the cost at time of purchase and a \$20 credit that is used for the next purchase. $\endgroup$
    – RobPratt
    May 31, 2020 at 19:39
  • $\begingroup$ Oh I see, you're counting each coupon received as spending minus \$20 on that purchase. But assuming you'll be able to recoup a \$20 on a \$5 purchase is a big if :-) I'd prefer to just spend \$1140 and keep the last \$20 coupon in reserve for the future, rather than potentially wasting \$5 at the end. Our answers are essentially the same then, bar some lawyering about when coupons can be used. $\endgroup$
    – Rand al'Thor
    May 31, 2020 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.