The number of bottles of beer one can buy with $10, after exchanging bottles and caps

Question

My answer to this question is 15, but my dad insists I am wrong. Who is right?

$2 can buy 1 bottle of beer.
4 bottle caps can be exchanged for 1 bottle beer.
2 empty bottles can be exchanged for 1 bottle of beer.

How many bottles of beer can you buy with $10?

I feel like some of the answers I've gotten so far... don't really make sense or really follow what I am trying to ask.

So I think I will clarify what I am trying to ask for.

YOU CAN (have to) TRADE / EXCHANGE bottle caps and empty bottles to get new bottles.

So how many can you buy with $10?

The answer he got is 20, which is correct. I just don't understand why.

Answer 1

I would show your dad the following table which should be easy to follow line by line:

$$ \begin{array}{|c|c|c|} \hline \text{Full Beers} & \text{Empty Bottles} & \text{Caps} & \text{Action}\\ \hline \color{red}{5} & 0 & 0 & \text{DRINK} \\ 0 & 5 & 5 & \text{Buy more}\\ \color{red}{3} & 1 & 1 & \text{DRINK}\\ 0 & 4 & 4 & \text{Buy more}\\ \color{red}{3} & 0 & 0 & \text{DRINK}\\ 0 & 3 & 3 & \text{Buy more}\\ \color{red}{1} & 1 & 3 & \text{DRINK}\\ 0 & 2 & 4 & \text{Buy more}\\ \color{red}{2} & 0 & 0 & \text{DRINK}\\ 0 & 2 & 2 & \text{Buy more}\\ \color{red}{1} & 0 & 2 & \text{DRINK}\\ 0 & 1 & 3 & \text{Insufficient funds}\\ \hline \end{array} $$

$$\color{red}{\text{Total beers} : 5+3+3+1+2+1=15}$$

Depending on how we interpret the rules there are some caveats to this solution:

1. (Suggested by Ross Millikan) If we can exchange $2$ caps + $1$ bottle (which has the same monetary value as $4$ caps or $2$ bottles) then we can increase the total to $16$.
2. (Suggested by Peter Shor) If we are able to borrow one cap then we can buy one more beer from our $4$ caps and return the borrowed cap immediately. This also gives us two empty bottles which can be used to buy a new beer which brings the total to $17$. If we are then allowed to borrow a bottle we can buy even another beer and return the bottle we borrowed giving us a total of $18$ beers.
3. (Suggested by Henry) Combining the two suggestions above, i.e. allowing borrowing and using $1$ bottle + $2$ caps as currency to buy a new beer we can get up to $20$ which is the theoretical maximum. This is shown below where the first line is the last line of the table above.

$$ \begin{array}{|c|c|c|} \hline \text{Full Beers} & \text{Empty Bottles} & \text{Caps} & \text{Action}\\ \hline \ldots & \ldots & \ldots & \ldots \\ 0 & 1 & 3 & \text{Borrow cap}\\ 0 & 1 & 4 & \text{Buy more}\\ \color{red}{1} & 1 & 0 & \text{DRINK}\\ 0 & 2 & 1 & \text{Return cap}\\ 0 & 2 & 0 & \text{Buy more}\\ \color{red}{1} & 0 & 0 & \text{DRINK}\\ 0 & 1 & 1 & \text{Borrow bottle}\\ 0 & 2 & 1 & \text{Buy more}\\ \color{red}{1} & 0 & 1 & \text{DRINK}\\ 0 & 1 & 2 & \color{black}{\text{Buy more}}\\ \color{red}{1} & 0 & 0 & \text{DRINK}\\ 0 & 1 & 1 & \text{Borrow cap}\\ 0 & 1 & 2 & \color{black}{\text{Buy more}}\\ \color{red}{1} & 0 & 0 & \text{DRINK}\\ 0 & 1 & 1 & \text{Return bottle and cap}\\ 0 & 0 & 0 & \text{Insufficient funds}\\ \hline \end{array} $$

$$\color{red}{\text{Total beers} : 15 + 1 + 1 + 1 + 1 + 1 = 20}$$

---

For the general problem: each beer you drink can be used to buy $\frac{3}{4}$ more beers so in general we expect that if you start with $B$ beers then you will be able to drink a total of

$$B\left(1+\frac{3}{4}+\left(\frac{3}{4}\right)^2 + \ldots\right) = 4B \text{ beers}$$

A quick check on the computer gives us the formula $4B - 5 \text{ beers}$ (without bending the rules) and $4B$ when bending the rules (as in 3. above) holds for all $B\in [2,1000]$.

Answer 2

"Aleph-null bottles of beer on the wall, Aleph-null bottles of beer, Take one down, and pass it around, Aleph-null bottles of beer on the wall" (repeat). -- Renteln and Dundes (2005) (link)

Mathematical Model

State: (a state is a description of what is)

• $u = (b, d, f, c, e)$ contains the budget $b$, the number of drunken bottles $d$, the number of full bottles $f$, the number of caps $c$ and the number of empty bottles $e$
• $u \ge 0$
• $u \in \mathbb{Z}^5$

Initial values: (the start state) $$ u_0 = (10, 0, 0, 0, 0)^\top \quad (A) $$ We start with $\$10$ and nothing else.

Actions: (an action changes a situation into another)

We have one of these basic actions per round, which change a state $u_i$ into the new state $u_{i+1}$ via $$ u_{i+1} = u_i + \Delta u $$

• buying one bottle of beer leads to:
  $q: \Delta u = (-2, 0, 1, 0, 0)$
• exchanging four caps into one beer leads to:
  $r: \Delta u = (0, 0, 1, -4, 0)$
• exchanging two empty bottles for one full bottle:
  $s: \Delta u = (0, 0, 1, 0, -2)$
• drinking a bottle of beer:
  $t: \Delta u = (0, 1, -1, 1, 1)$

Formulation as a Linear Program

We select up to one out of four actions $\{ q,r,s,t \}$ through variables $a_i = (q_i, r_i, s_i, t_i) \in \{0, 1\}^4$ and requiring $$ q_i + r_i + s_i + t_i \le 1 \quad (B) $$

The actions work on the states like \begin{align} b_i &= b_{i-1} - 2 q_i \\ d_i &= d_{i-1} + t_i \\ f_i &= f_{i-1} + q_i + r_i + s_i - t_i \quad (C) \\ c_i &= c_{i-1} - 4 r_i + t_i \\ e_i &= e_{i-1} - 2 s_i + t_i \end{align}

With this we are able to model a complete run from start state $u_0$ to a final state $u_k$, caused by $k$ applied actions $a_i$: $$ u_0 \overset{a_1}{\to} u_1 \overset{a_2}{\to} u_2 \cdots u_{k-1} \overset{a_k}{\to} u_k $$ We assemble the vector $x$ as: $$ x = ( u_0^\top, a_1^\top, u_1^\top, a_2^\top, u_2^\top, \ldots, a_r^\top, u_r^\top)^\top $$ where $k \le r$ is the maximum number of rounds we allow $x$ to represent.

Then we can formulate the problem as boolean integer linear program \begin{array}{rl} \max & c^\top \, x \\ \text{w.r.t.} & A x = u_0 \\ & B x \le y \\ & C x = 0 \\ & x \ge 0 \end{array} where $c$ is choosen to have $1$ components matching the $t_i$ variables within the $a_i$, to count the drunken beer, $x$ is the vector of $5+5r$ integer variables and $4r$ Boolean variables. The matrices $A, B, C$ and the vector $y$ model the constraints $(A)$, $(B)$ and $(C)$.

The program should find out what maximum can be reached in $r$ rounds of action or less. If $r$ is chosen such large, that all actions seem covered and such small, that memory and execution time will not explode, this plan should work. (Mad laughter)

I'll give it a try after a beer.

Implementation

We use the R language to interface to the lpsolve Mixed Integer Linear Programming solver.

Setting up the above model leads to this R program: (lp-beer.R)
This is a full output: (lp-beer.log)
This is the model in lp-format: (model.txt)

Note how the above model and its constraints show up in the R program and the lp-format model.

Computational Results:

Here is the result for $r=30$, $n = 155 + 120 = 275$ variables:

Objective: 15 
(u 0: 10 0 0 0 0
|a 1 : BUY |u 1 : 8 0 1 0 0
|a 2 : DRINK |u 2 : 8 1 0 1 1
|a 3 : BUY |u 3 : 6 1 1 1 1
|a 4 : BUY |u 4 : 4 1 2 1 1
|a 5 : BUY |u 5 : 2 1 3 1 1
|a 6 : DRINK |u 6 : 2 2 2 2 2
|a 7 : EXC E |u 7 : 2 2 3 2 0
|a 8 : DRINK |u 8 : 2 3 2 3 1
|a 9 : DRINK |u 9 : 2 4 1 4 2
|a 10 : DRINK |u 10 : 2 5 0 5 3
|a 11 : EXC E |u 11 : 2 5 1 5 1
|a 12 : EXC C |u 12 : 2 5 2 1 1
|a 13 : DRINK |u 13 : 2 6 1 2 2
|a 14 : DRINK |u 14 : 2 7 0 3 3
|a 15 : EXC E |u 15 : 2 7 1 3 1
|a 16 : DRINK |u 16 : 2 8 0 4 2
|a 17 : EXC E |u 17 : 2 8 1 4 0
|a 18 : DRINK |u 18 : 2 9 0 5 1
|a 19 : EXC C |u 19 : 2 9 1 1 1
|a 20 : DRINK |u 20 : 2 10 0 2 2
|a 21 : EXC E |u 21 : 2 10 1 2 0
|a 22 : BUY |u 22 : 0 10 2 2 0
|a 23 : DRINK |u 23 : 0 11 1 3 1
|a 24 : DRINK |u 24 : 0 12 0 4 2
|a 25 : EXC E |u 25 : 0 12 1 4 0
|a 26 : DRINK |u 26 : 0 13 0 5 1
|a 27 : EXC C |u 27 : 0 13 1 1 1
|a 28 : DRINK |u 28 : 0 14 0 2 2
|a 29 : EXC E |u 29 : 0 14 1 2 0
|a 30 : DRINK |u 30 : 0 15 0 3 1)

This is the result for $r = 31$, $n = 160 + 124 = 284$ variables:

Objective: 15 
(u 0: 10 0 0 0 0
|a 1 : BUY |u 1 : 8 0 1 0 0
|a 2 : BUY |u 2 : 6 0 2 0 0
|a 3 : BUY |u 3 : 4 0 3 0 0
|a 4 : BUY |u 4 : 2 0 4 0 0
|a 5 : DRINK |u 5 : 2 1 3 1 1
|a 6 : DRINK |u 6 : 2 2 2 2 2
|a 7 : DRINK |u 7 : 2 3 1 3 3
|a 8 : EXC E |u 8 : 2 3 2 3 1
|a 9 : DRINK |u 9 : 2 4 1 4 2
|a 10 : DRINK |u 10 : 2 5 0 5 3
|a 11 : EXC E |u 11 : 2 5 1 5 1
|a 12 : EXC C |u 12 : 2 5 2 1 1
|a 13 : DRINK |u 13 : 2 6 1 2 2
|a 14 : DRINK |u 14 : 2 7 0 3 3
|a 15 : EXC E |u 15 : 2 7 1 3 1
|a 16 : DRINK |u 16 : 2 8 0 4 2
|a 17 : EXC E |u 17 : 2 8 1 4 0
|a 18 : DRINK |u 18 : 2 9 0 5 1
|a 19 : EXC C |u 19 : 2 9 1 1 1
|a 20 : DRINK |u 20 : 2 10 0 2 2
|a 21 : BUY |u 21 : 0 10 1 2 2
|a 22 : EXC E |u 22 : 0 10 2 2 0
|a 23 : NOP |u 23 : 0 10 2 2 0
|a 24 : DRINK |u 24 : 0 11 1 3 1
|a 25 : DRINK |u 25 : 0 12 0 4 2
|a 26 : EXC E |u 26 : 0 12 1 4 0
|a 27 : EXC C |u 27 : 0 12 2 0 0
|a 28 : DRINK |u 28 : 0 13 1 1 1
|a 29 : DRINK |u 29 : 0 14 0 2 2
|a 30 : EXC E |u 30 : 0 14 1 2 0
|a 31 : DRINK |u 31 : 0 15 0 3 1)

For $r = 32$ things start to get slow. The solver has not terminated after 10 min.

Answer 3

$10 can get you 5 bottles. From 5 bottles you get 5 caps and 5 empty bottles. Using 4 caps and 4 empty bottles you can get 3 new bottles and you are left with 1 cap and 1 empty bottle(8 bottles bought so far).3 new bottles give you 3 caps and 3 empty bottles and with leftovers you have 4 caps and 4 empty bottles in total. 4 caps and 4 empty bottles give you 3 new bottles (11 bottles so far).3 new bottles provides you 3 caps and 3 empty bottles, so you can get 1 new bottles and be left will 3 caps and 1 empty bottle(12 bottles so far). Now that one bottle provides 1 cap and 1 empty bottle and with leftovers you have 4 caps and 2 empty bottles. These provide you with 2 new bottles (14 bottles so far). 2 new bottles give you 2 caps and 2 empty bottles. 2 empty bottles give you 1 new bottle (15 in total so far). So now you are left with 3 caps and 1 empty bottle which cannot buy you a new bottle or bottles.

Answer 4

If $m$ is the number of beer bottles initially purchased and $N$ is the total number of beer bottles that can be bought or exchanged, then we have $m+\left\lfloor \frac{N-1}2\right\rfloor+\left\lfloor\frac{N-1}4\right\rfloor \geq N$. That is, $N\leq 4m-5$ or $N=4m-3$. The case where $N=4m-3$ happens only when there are $1$ empty bottle and $1$ bottle cap left, which can only happen when $m=1$. (To show this, suppose that the beer is drunk immediately after a purchase or an exchange. Then, at no point in time after the first purchase do we have the number of empty bottles or the number of bottle caps to be $0$.) Hence, if $m>1$, $N\leq 4m-5$. For $m=5$, we have $N\leq 15$. (It can be proven by induction on $m>1$ that this bound is sharp.)

Now, if borrowing empty bottles and bottle caps is allowed, then we need $m+\left\lfloor{\frac{N}{2}}\right\rfloor+\left\lfloor{\frac{N}{4}}\right\rfloor \geq N$. That is, $N\leq 4m$. We can show by induction on $m$ that this bound is sharp. Perhaps nonsurprisingly, you only need to borrow $1$ empty bottle and $3$ bottle caps in all cases.

However, if an empty bottle can be returned for $\$1.00$ and a bottle cap can be returned for $\$0.50$, then $\frac x2+\frac{N-1}2+\frac{N-1}4\geq N$, where the initial fund is $\$x$. Therefore, $N\leq 2x-3$. This bound is sharp for all integers $x \geq 2$ and for all half-integers $x\geq \frac32$. (In this scenario, if you can also borrow empty bottles and empty caps, then $N\leq 2x$ for all nonnegative integers $x$ and for every half-integer $x\geq \frac{1}{2}$. The bound is again sharp and you need to only borrow $1$ empty bottle and $1$ bottle cap in all cases.)

Answer 5

Executive summary: As originally posed, assuming no transactions that are not explicitly allowed by the problem statement, starting with just $\$10$ you can drink $15$ beers but no more.

If you are allowed to borrow empty bottles and caps (which you must return at the end), you can drink $20$ beers. If no other kinds of transaction are assumed, you must borrow at least $3$ items, but $1$ empty and $2$ caps will be sufficient.

If borrowing (as described above) is allowed and you can redeem $1$ empty and $2$ caps for one full bottle of beer, you must borrow at least $1$ empty and at least $1$ cap in order to drink $20$ bottles, but $1$ empty and $1$ cap are sufficient.

---

Original answer:

Since there is no real choice about what to do with empty bottles (other than hoard them or trade pairs of them for full bottles) and likewise no real choice about what to do with caps, a greedy algorithm is optimal. In fact, any algorithm at all is optimal as long as you don't stop while still in possession of either $\$2$, two bottles, or four caps.

Represent a state by $(m,e,c,d)$ where $m$ is your cash in dollars, $e$ is the number of empty bottles you have, $c$ is the number of caps you have, and $d$ is the number of bottles you have drunk. Assume you drink every bottle as soon as you acquire it. Then the possible transitions and the conditions under which they can occur are

\begin{array}{rcll} (m,e,c,d) & \to & (m-2, e + 1, c + 1, d + 1) &\qquad\text{if $m\geq 2$}\\ (m,e,c,d) & \to & (m, e - 1, c + 1, d + 1) &\qquad\text{if $e\geq 2$} \\ (m,e,c,d) & \to & (m, e + 1, c - 3, d + 1) &\qquad\text{if $c\geq 4$} \\ \end{array}

The "any algorithm works" principle means that you do not have to spend all the money before trading. So let's follow this algorithm: whenever a transition leaves us with two empties, trade them, and whenever a transition leaves us with four caps, trade them.

Every purchase of a new bottle with cash will therefore be followed immediately by zero or more trades that stop only when $e < 2$ and $c < 4$.

It is then simple to see how this algorithm plays out, starting with $m$ dollars:

\begin{array}{lcl} (m, 0, 0, 0) & \to & (m - 2, 1, 1, 1) \\ (m - 2, 1, 1, 1) & \to & (m - 4, 2, 2, 2) \\ (m - 4, 2, 2, 2) & \to & (m - 4, 1, 3, 3) \\ (m - 4, 1, 3, 3) & \to & (m - 6, 2, 4, 4) \\ (m - 6, 2, 4, 4) & \to & (m - 6, 1, 5, 5) \\ (m - 6, 1, 5, 5) & \to & (m - 6, 2, 2, 6) \\ (m - 6, 2, 2, 6) & \to & (m - 6, 1, 3, 7) \\ \end{array}

After drinking $7$ bottles, we do not have enough things to trade, so we repeat the last four transitions, buying another bottle for cash and then trading down our empties and bottle caps until we have only one empty and three caps. Each time we do this, we drink $4$ more bottles of beer. We finally stop when we gave $1$ empty and $3$ caps and the remaining amount of cash is less than $2$.

So for any initial amount of cash $m$, we will be able to buy $B = \lfloor m/2 \rfloor$ bottles of beer for cash, and if $B \geq 2$, by induction (using the result of the third transition in the sequence above as our base case) we will drink $4B - 5$ bottles. (This formula clearly does not work if $B < 2$, but that leaves only two special cases that are easy to solve.) For $m=10$, we have $B = 5$ and therefore we can drink $4\times5 - 5 = 15$ bottles.

---

First Addendum:

The alleged answer $20$ comes from the fact that on average, when you are able to buy a lot of bottles, the bottles end up costing $\$0.50$ each after trading back the empties and the bottle caps: each new bottle you buy produces one empty bottle (worth $\$1$, because you can trade two of them for a two-dollar bottle of beer) and one cap (worth $\$0.50$, because you can trade four of them for a bottle of beer). And as we can see, each bottle we buy after the first bottle allows us to drink four bottles: the bottle we just bought, plus three others obtained by trading in empties and bottle caps.

And $20$ would be the correct answer if we could trade fractional objects for fractional objects, for example, if you could trade $1/4$ bottle cap (equal to $4/16$ of a cap) for $1/16$ full bottle of beer. But this is not a plausible interpretation of the problem. (You would also have to make infinitely many trades in order to consume $20$ complete bottles of beer rather than, say, just $19\frac{15}{16}$ bottles, but let's not even get into that; fractional bottles are just a non-starter.)

Taking into account the idea that you can only trade whole empties and whole caps for whole bottles, if you buy at least one bottle for cash you will inevitable end up with some empties and caps that you are unable to redeem for new bottles. Specifically, if you buy more than two bottles for cash, you will be left with $1$ empty and $3$ caps, valued at $\$2.50$ total (if you had something to combine with them in trade), representing the $5$ full bottles of beer that you will be unable to obtain.

So your father is wrong, or rather, he has given an answer that can be justified only if you make some very silly assumptions (such as the assumption that you can trade one empty bottle for an object containing $1/2$ as much beer as a full bottle, held inside $1/2$ of a bottle by $1/2$ of a bottle cap).

---

Second Addendum:

It has been pointed out that if you can borrow empty bottles and caps, you can drink $5$ more bottles of beer than are allowed under the assumptions above, and have enough empty bottles and caps at the end to be able to return all the things you borrowed.

This is changing the question, because it introduces actions the original question does not say was possible: there are various ways we can do that in order to make it possible to drink $20$ bottles of beer for $\$10$ (for example, someone could offer to redeem empties and caps for cash because they can use them to get beer, and someone else might be willing to lend us money). But it leads to an interesting follow-up question: given only the added assumption that it is possible to borrow some number of bottles and caps, what is the minimum number of bottles and caps we have to borrow in order to be able to drink $20$ bottles?

We must borrow at least one empty and one cap, because the last action we will take will involve returning the empty bottle and cap of the last bottle we drink. But if that is all we borrow, then starting with $\$10$, after having drunk the first $15$ beers and having borrowed the items (not necessarily in that order) we find ourselves in the state $(0,2,4,15)$, and as we can see from the earlier exercise, the furthest we can get from this is $(0,1,3,18)$.

But suppose instead we borrow $1$ empty and $2$ caps. Then after having drunk the first $15$ beers and having borrowed the items, we can proceed as follows:

\begin{array}{lcl} (0, 2, 5, 15) & \to & (0, 1, 6, 16) \\ (0, 1, 6, 16) & \to & (0, 2, 3, 17) \\ (0, 2, 3, 17) & \to & (0, 1, 4, 18) \\ (0, 1, 4, 18) & \to & (0, 2, 1, 19) \\ (0, 2, 1, 19) & \to & (0, 1, 2, 20) \end{array}

After the last step we can return the borrowed items and have no empties or caps left over.

Since borrowing a total of two items or fewer is insufficient, and this method borrows a total of only three items, I believe this is a minimal solution. Moreover, the three items have the minimum possible value. (Any solution must borrow at least one empty bottle.)

But if we are allowed to trade one empty bottle and two caps for a full bottle of beer, as suggested in another answer, we can drink $20$ bottles for $\$10$ by borrowing just one empty and one cap. The last few steps then are

\begin{array}{lcl} (0, 2, 4, 15) & \to & (0, 1, 5, 16) \\ (0, 1, 5, 16) & \to & (0, 2, 2, 17) \\ (0, 2, 2, 17) & \to & (0, 1, 3, 18) \\ (0, 1, 3, 18) & \to & (0, 1, 2, 19) \qquad \text{by redeeming $1$ empty and $2$ caps} \\ (0, 1, 2, 19) & \to & (0, 1, 1, 20) \qquad \text{by redeeming $1$ empty and $2$ caps} \end{array}

After this we return the empty bottle and cap we borrowed.

Answer 6

If you are allowed to borrow stuff, then you can get to drink $20$ bottles of beer:

• Buy $5$ bottles of beer for $\$10$
• Drink $5$ bottles of beer, giving you $5$ empty bottles and $5$ caps
• Borrow $15$ empty bottles and $15$ caps, giving you $5+15=20$ empty bottles and $5+15=20$ caps in total
• Swap the $20$ empty bottles for $\frac{20}{2}=10$ bottles of beer and swap the $20$ caps for $\frac{20}{4}=5$ bottles of beer, giving you $10+5=15$ bottles of beer
• Drink $15$ bottles of beer, giving you $15$ empty bottles and $15$ caps
• Repay the $15$ empty bottles and $15$ caps that you previously borrowed

In total you have drunk $5+15 = 20$ bottles of beer. So your dad may therefore be correct even if he is raising an alcoholic.

If you cannot borrow, than your final bottle of beer will leave you with an empty bottle and and a cap which combined are worth about $\$0.375$, which you cannot turn into beer, and so $20$ bottles of beer at an average cost of $\frac{\$10}{20}=\$0.50$ would not be possible.

Answer 7

Similar as in other answers, a state is described by a tuple $(z,m,b,e,c)$ where $z=$ number of bottles drunk, $m=$ available money in dollars, $b=$ full bottles in inventory, $e=$ empty bottles i inventory, $c=$ caps in inventory. The followig steps can be applied, each adding a specific tuple to the current tuple:

• Buy a bottle: $(0,-2,+1,0,0)$
• Drink a bottle: $(+1,0,-1,+1,+1)$
• Trade two empty bottles: $(0,0,+1,-2,0)$
• Trade four caps: $(0,0,+1,0,-4)$

We start with the tuple $(0,10,0,0,0)$ and are allowed to apply the above steps in any order, provided that no component ever becomes negative, and our goal is to maximze the $z$ component. Among all step sequences that lead to the maximal possible $z$, consider one that minimizes the sum of the index positions in the sequence where we execute a "drink" step.

Then before each drink step we have $b=1$: Certainly $b\ge 1$ as otherwise we cannot drink. On the other hand, if for some dringk steps $b\ge 2$, consider the first drink step applied to a state with $b\ge2$. Then the preceding step (which must exist because initially $b=0$) must be a buy or trade step, and it is possible to swap the order of these two steps without changing the final result, contradicting the minimality of drink-index sum.

On the other hand, we certainly have $b=0$ after the last step as otherwise we could have yet another drink, contradicting optimality of the sequence. Since the only possible way to reach $b\le 1$ from $b\ge2$ would be drinking and drinking occurs only at $b=1$, we conclude that $b\ge 2$ never holds. Therefore, the four possible steps occur only in the following combinations:

• Buy and drink: $(1,-2,0,1,1)$
• Trade bottles and drink: $(1,0,0,-1,1)$
• Trade caps and drink: $(1,0,0,1,-3)$

By repeating the argument with a sequence that minimizes the sum of indices where we "buy and drink" among all double step sequences leading to optimal $z$, we see that "buy and drink" can always be swapped before any preceeding "trade bottles/caps and drink" (simply because the only thing it decreases, $m$, is not changed by the other double steps). Thus we may assume that we start with a few (by optimality: five) "buy and drink" double steps and after that only "trade and drink". So essentially, we start with $(5,0,0,5,5)$ and can apply only $(1,0,0,-1,1)$ (provided $e\ge2$) or $(1,0,0,1,-3)$ (provided $c\ge 4$) from then on.

By induction, we conclude that $e\equiv c\pmod 2$ throughout, because neither of the two trading double steps changes this fact. Likewise by induction, $z+2e+c=20$ and $e\ge1$ and $c\ge 1$. Using $e\ge1, c\ge1$ the next thing we show by induction is $e+c\ge 3$: It holds initlyy when $c=e=5$ and it holds after each trade doublke step because one of te numbers is increased from being $\ge1$ before the double step and the other is $\ge1$ anyway.

After the final step we have $e=1$ by optimality because $e\ge2$ would allow us to get yet another drink. Similary, $1\le c\le 3$ after the final step. As $e\equiv c\pmod 2$ and $e+c\ge 2$, we conclude $c=3$. Therefore in the end $$z=18-e-c=15.$$