Can this problem be generalised mathematically?

I found a mathematical riddle which I solved by experiment and I would like to know is there a formula of some sort to solve these kind of problems.

You have 10 Euro. You can buy a bottle of beer for 1 Euro. You can exchange 2 empty bottles for 1 new full bottle. What is the maximum number of bottles that you can go through for your 10 Euro ?

By experiment you can go through 19 bottles for the 10 Euro.

But is there some formula to obtain 19 from the initial conditions ? I thought maybe something related to sequences or some kind of limit.

Any ideas?

Solution 1:

A bottle is 50 cents and the beer in the bottle is also 50 cents.

In the end you will have one empty bottle left, that means you spent 9.50 on the beer you drank.

With 50 cents for a beer this means you drank 19 beers.

Solution 2:

You could express this with sequences, but it's more elegant not to. Basically, it's important to recognize that it doesn't matter when or how you got the empty bottles - it just matters how many there are - and this idea does not need sequences to express.

Let us consider the situation after you have drunk the first $10$ bottles. In particular, let us group together a bunch of consecutive actions into one more manageable action:

If you have at least $2$ empty bottles, you can exchange $2$ bottles for a full one; after you drink this, you have drunk one more bottle, but have one less empty bottle.

Observe that if you repeat this step $m$ times, you will have $10-m$ empty bottles remaining. The first $m$ for which you may not make the exchange is the first for which $10-m<2$. The first such $m$ is $9$, so you can do this $9$ times.

Then, when you add this to the original $10$ full bottles, you get the correct $19$ bottles of beer drunk.

The steps of this proof generalize well; if you start with $N$ bottles and can exchange $a$ empty ones for $b$ full ones, where $b<a$, then, whenever you have $n\geq a$ bottles, you can drink $b$ more beers at the cost of having $a-b$ less beers. You can use this step $m$ times where $m$ is the first integer such that $N-(a-b)m<a$. That is, the first integer such that $m>\frac{N-b}{a-b}$, which is given by $m=\left\lfloor\frac{N-b}{a-b}\right\rfloor+1$. Then, the total number of beers drunk is $$N+b\left(\left\lfloor\frac{N-a}{a-b}\right\rfloor+1\right)$$ where $\lfloor\cdot\rfloor$ is the floor function, giving the first integer less than the argument.

Solution 3:

With $n$ € you can get $2n-1$ beers.

• For $n$ € you buy and drink $n$ beers, and you have $n$ empty bottles.
• Then you take two bottles $(-2)$, exchange them for a full one, drink it and add an emptied bottle to the collection $(+1)$. You have drunk one more beer and you're left with one less bottle.
• While iterating, you loose one empty bottle per each beer drank.
• Finally you stop with the last single bottle.

So you have exchanged $(n-1)$ empty bottles for $(n-1)$ beers, hence you had $n+(n-1)=2n-1$ beers and one empty bottle remains.

Solution 4:

This is a partial answer. Suppose you have $n$ dollars to begin with. Then you may purchase initially, $n$ bottles of beer. This gives you $n$ empty bottles, which you may then exchange towards $n/2$ new beers. The new beers in turn give you $n/2$ empty bottles, which you can exchange towards $n/4$ new bottles.

Ignoring the fact that the number of bottles are integer valued, to first approximation we have a total number of

$$n + n/2 + n/4 + n/2 + \cdots = 2n$$

bottles. Since you began with $n=10$, this approximation will give you $20$ total bottles, which is quite close to your actual value of $19$. The error stems from the fact that we must round down to the nearest integer at each step

$$n + \left\lfloor n/2 \right\rfloor + \left\lfloor n/4 \right\rfloor + \left\lfloor n/8 \right\rfloor + \cdots$$

This series can (sort of) be written in closed form. It is given by

$$n + \left\lfloor n/2 \right\rfloor + \left\lfloor n/4 \right\rfloor + \left\lfloor n/8 \right\rfloor + \cdots = 2n-s_n$$ where $s_n$ is the number of $1$s in the base-$2$ representation of $n$.

For our case, $10=(1010)_2$, so that $s_{10}=2$, and we have $2n-s_n = 18$. Again, this is not exact since we forgot to account for remainders when we took the floors. This serves as a lower bound for us. All of this so far shows that the actual number of bottles $B(n)$ is bounded above and below by

$$2n-s_n \le B(n) \le 2n.$$

Since $s_n \in \mathcal{O}(\log_2(n))$, we have that $B(n) \sim 2n$ as $n\rightarrow \infty$ (for the heavy drinkers out there).

It may be difficult to get a more fine-grained answer than this since it will depend on the divisibility properties of $n$. For example, we will have $B(2n) = 2n-1$ exactly for $n=2^k$. I certainly wouldn't expect a nice closed form formula for $B(n)$.