The number of bottles of beer one can buy with $10, after exchanging bottles and caps [closed]
Solution 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:
- (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$.
- (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.
- (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]$.
Solution 2:
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.
Solution 3:
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.)