10
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ "No single bottles remaining": does this mean that you end without drinking the last bottle? $\endgroup$ – abiessu Jul 19 '17 at 0:05
  • 2
    $\begingroup$ if you had a geometric series, you would find an upper bound of 20 but that allows partial bottles. $\endgroup$ – user451844 Jul 19 '17 at 0:05
  • 1
    $\begingroup$ because, you can't always hit half dead on unless you start with a power of two in this case. so in the geometric series you would get 10+5+2.5+1.25 and continue on forever to get 20 . in the series you want you would get 10+5+2+1+1 = 19 . $\endgroup$ – user451844 Jul 19 '17 at 0:25
  • 1
    $\begingroup$ Borrow an empty bottle, buy a new one, drink it and return the bottle you borrowed for a total of $20$. Related question: The number of bottles of beer one can buy with $10, after exchanging bottles and caps $\endgroup$ – Winther Jul 19 '17 at 0:55
  • 1
    $\begingroup$ It looks like nobody has yet pointed out that in the original problem, if you start with $n$ Euro (where $n$ is a positive integer), the number of bottles you can drink is always $2n - 1$. $\endgroup$ – Tanner Swett Jul 19 '17 at 1:45
12
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ That's the right idea, but (as written) it doesn't prove that $2n-1$ is the maximum. $\endgroup$ – dxiv Jul 20 '17 at 6:46
  • 1
    $\begingroup$ ugh..imagine the hangover $\endgroup$ – Alvin Lepik Jul 20 '17 at 6:50
  • 1
    $\begingroup$ @dxiv Then see the answer by Leonhard. $\endgroup$ – CiaPan Jul 20 '17 at 6:50
21
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ With this simple method, you can complete the calculation even mid-experiment ... :) $\endgroup$ – Hagen von Eitzen Jul 19 '17 at 10:07
  • 2
    $\begingroup$ +1 for a very clever observation that price of beer+bottle = twice the bottle's price! $\endgroup$ – CiaPan Jul 19 '17 at 12:09
  • 2
    $\begingroup$ I think this only works for integer numbers of euros, since you can't exchange 50 cents and one bottle for a new beer. But if step one is "floor your money" this should work. $\endgroup$ – undergroundmonorail Jul 19 '17 at 14:25
  • 2
    $\begingroup$ I wonder why the question always starts with the amount of money you have, instead of just 10 beers. It's not like there could be any other means of spending the money, (barring this nice observation of course). $\endgroup$ – xiaomy Jul 19 '17 at 19:10
12
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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)$.

$\endgroup$
  • 1
    $\begingroup$ This answer isn't right; it doesn't take into account that you can hold onto empty bottles in this exchanging process even if you can't use them immediately. Seeing this, $B(n)$ always equals $2n-1$ in this case. Try the case of $3$ bottles for instance. $\endgroup$ – Milo Brandt Jul 19 '17 at 1:01
3
$\begingroup$

The money is just a red herring here. Let's assume you start with the full bottles. In what follows, let $[x]$ denote the ``floor'' function; i.e., $[x]$ is the largest integer $\leq x$.

In general, however many full bottles you begin with, keep track of two quantities: $F_{N} = \left[ N / 2 \right]$ full bottles obtainable from drinking the previously given batch and $$ E_{N} = N - 2 \left[ N / 2 \right] $$ empty bottles.

Thus, at each iteration one keeps track of $F_{N}$ and of the cumulative sum of the $E_{N}$'s. If that sum is $\geq 2$ at step $N$, then the appropriately many of the $\sum_{k=1}^{N} E_{k}$ empty bottles get converted to twice as few full bottles, which affects $F_{N+1}$ and gives $$ E_{N+1} = \sum_{k=1}^{N} E_{k} - 2 \left[ \sum_{k=1}^{N} E_{k} \right]. $$

$\endgroup$
3
$\begingroup$

Here's a generalization:

You have $A$ euros and can buy a bottle for $x$ euros. You can return $n$ bottles to get $y$ euros back. How many bottles can you go through?

If $A<nx$, we will only be able to buy $\left\lfloor\dfrac{A}{x}\right\rfloor$ bottles .If $y\geq nx$, we will be making (or at least not spending) money when we return the bottles, so we will be able to buy infinitely many.

So we assume $A\geq nx>y$.

The order in which you buy and return bottles does not matter, so let's return bottles whenever we can.

We start with $A$ euros. We buy $n$ bottles, return them and get $y$ euros back, so we end up with $A-nx+y=A-(nx-y)$. Keeping this procedure, we will buy another $n$ bottles, return them and end up with $A-2(nx-y)$ euros and so on. Continuing this procedure, we will have had $nk$ bottles and have $A-k(nx-y)$ euros.

When $A-k(nx-y)$ is smaller than $nx$ we won't be able to buy $n$ bottles anymore. Since $k$ is integer, $$A-k(nx-y)\leq nx\iff k>\dfrac{A-nx}{nx-y}\iff k\geq\left\lfloor\dfrac{A-nx}{nx-y}\right\rfloor+1=\left\lfloor\dfrac{A-y}{nx-y}\right\rfloor$$

So we can buy $n\cdot\left\lfloor\dfrac{A-y}{nx-y}\right\rfloor$ bottles and end up with $A-\left\lfloor\dfrac{A-y}{nx-y}\right\rfloor(nx-y)$ euros, which we can then use to buy another $\left\lfloor\left(A-\left\lfloor\dfrac{A-y}{nx-y}\right\rfloor(nx-y)\right)/x\right\rfloor$ bottles.

Therefore, letting $a=\left\lfloor\dfrac{A-y}{nx-y}\right\rfloor$, we can buy $na+\left\lfloor\dfrac{A-a(nx-y)}{x}\right\rfloor=\left\lfloor\dfrac{A+ay}{x}\right\rfloor$ bottles.


In the problem you wrote: $A=10$, $n=2$, $x=y=1$, so $a=\left\lfloor\dfrac{10-y}{2-1}\right\rfloor=9$, so we can buy $$\left\lfloor\dfrac{A+ay}{x}\right\rfloor=\left\lfloor\dfrac{10+9\cdot1}{1}\right\rfloor=19$$ as we expected.

$\endgroup$
  • 1
    $\begingroup$ You can use $\LaTeX$ modifiers \left and \right to paren-like symbols to make them adjust to the contents size. Compare \lfloor\frac AB\rfloor → $\lfloor\frac AB\rfloor$ and \left\lfloor\frac AB\right\rfloor → $\left\lfloor\frac AB\right\rfloor$ $\endgroup$ – CiaPan Jul 19 '17 at 12:12

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.