Can You Take Down All The Bottles Of Beer?

Riddler Classic

From Steven Brown comes a puzzle to take down and pass around:

You and your friends are singing the traditional song, “99 Bottles of Beer.” With each verse, you count down the number of bottles. The first verse contains the lyrics “99 bottles of beer,” the second verse contains the lyrics “98 bottles of beer,” and so on. The last verse contains the lyrics “1 bottle of beer.”

There’s just one problem. When completing any given verse, your group of friends has a tendency to forget which verse they’re on. When this happens, you finish the verse you are currently singing and then go back to the beginning of the song (with 99 bottles) on the next verse.

For each verse, suppose you have a 1 percent chance of forgetting which verse you are currently singing. On average, how many total verses will you sing in the song?

Extra credit: Instead of “99 Bottles of Beer,” suppose you and your friends are singing “N Bottles of Beer,” where N is some very, very large number. And suppose your collective probability of forgetting where you are in the song is 1/N for each verse. If it takes you an average of K verses to finish the song, what value does the ratio of K/N approach?

Solution

Let $f$ be the probability of forgetting for each verse.

1 Bottle of Beer

• You and your friends can finish on the first verse with probability $1-f$.
• You and your friends can forget on the first verse. Each time you forget on the first verse, the number of verses you have to sing increases by 1.

The expected value of finishing 1 Bottle of Beer is:

$$EV_1 = 1-f + f\cdot(1+EV_1)$$
$$EV_1 = 1 - f + f + f\cdot EV_1$$
$$EV_1 - f\cdot EV_1= 1$$
$$EV_1 = \dfrac{1}{1-f} = \dfrac{1}{f}\cdot\dfrac{f}{1-f} = \dfrac{1}{f}\left(\dfrac{1}{1-f} -1\right)$$

2 Bottles of Beer

• You and your friends can finish on the second verse with probability $(1-f)^2$.
• You and your friends can forget on the first verse. Each time you forget on the first verse, the number of verses you have to sing increases by 1.
• You and your friends can get the first verse correct, but forget on the second verse. Each time you forget on the second verse, the number of verses you have to sing increases by 2.

The expected value of finishing 2 Bottles of Beer is:

$$EV_2 = 2(1-f)^2 + f\cdot(1+EV_2) + (1-f)\cdot f \cdot(2+EV_2)$$
$$EV_2 = (2-4f+2f^2) + (f + f\cdot EV_2) + (2f -2f^2 + (f-f^2)\cdot EV_2)$$
$$EV_2 \cdot(1 - f - (f-f^2)) = 2-4f+2f^2 + f + 2f - 2f^2$$
$$EV_2 = \dfrac{2-f}{1-2f+f^2} = \dfrac{2-f}{(1-f)^2}$$
$$ = \dfrac{1}{f}\cdot\dfrac{2f-f^2}{(1-f)^2} = \dfrac{1}{f}\left(\dfrac{1}{(1-f)^2} -1\right)$$

b Bottles of Beer

• You and your friends can finish on the $b$^th verse with probability $(1-f)^b$.
• You and your friends can forget on the first verse. Each time you forget on the first verse, the number of verses you have to sing increases by 1.
• You and your friends can get the first verse correct, but forget on the second verse. Each time you forget on the second verse, the number of verses you have to sing increases by 2.
• ...
• You and your friends can get the first $b-2$ verses correct, but forget on the $b-1$^st verse. Each time you forget on the $b-1$^st verse, the number of verses you have to sing increases by $b-1$.
• You and your friends can get the first $b-1$ verses correct, but forget on the $b$^th verse. Each time you forget on the $b$^th verse, the number of verses you have to sing increases by $b$.

The expected value of finishing b Bottles of Beer is:

$$EV_b = b(1-f)^b + f\cdot(1+EV_b) + (1-f)\cdot f \cdot(2+EV_b) + \cdots (1-f)^{b-2}\cdot f \cdot(b-1+EV_b) + (1-f)^{b-1}\cdot f \cdot(b+EV_b)$$
$$EV_b = b(1-f)^b + \sum_{v = 1}^{b} \left((1-f)^{v-1}\cdot f\cdot (v + EV_b)\right)$$
$$EV_b = b(1-f)^b + f\cdot\sum_{v = 1}^{b} v(1-f)^{v-1} + f\cdot EV_b \cdot \sum_{v = 1}^{b} (1-f)^{v-1}$$
$$EV_b \left(1 - f\cdot \sum_{v = 1}^{b} (1-f)^{v-1}\right) = b(1-f)^b + f\cdot\sum_{v = 1}^{b} v(1-f)^{v-1}$$
$$EV_b \left(1 - f\cdot \sum_{v = 1}^{b} (1-f)^{v-1}\right) = b(1-f)^b + f\cdot \left(\sum_{v = 1}^{b} (1-f)^{v-1} + \sum_{v = 2}^{b} (1-f)^{v-1} + \cdots + \sum_{v = b}^{b} (1-f)^{v-1}\right)$$
Applying finite geometric sums:

$$EV_b \left(1 - f\cdot \dfrac{1-(1-f)^b}{1-(1-f)}\right) = b(1-f)^b + f\cdot \left(\dfrac{1-(1-f)^b}{1-(1-f)} + \dfrac{(1-f)\left(1-(1-f)^{b-1}\right)}{1-(1-f)} + \cdots + \dfrac{(1-f)^{b-1}\left(1-(1-f)^1\right)}{1-(1-f)}\right)$$
Applying $1-(1-f) = f$ and canceling.

$$EV_b \left(1 - \left(1-(1-f)^b\right)\right) = b(1-f)^b + f\cdot \left(\left(1-(1-f)^b\right) + \left((1-f)-(1-f)^b\right) + \cdots + \left((1-f)^{b-1}-(1-f)^b\right)\right)$$

$$EV_b \cdot (1-f)^b = b(1-f)^b +\sum_\limits{v = 1}^{b} (1-f)^{v-1} - b(1-f)^b$$
$$EV_b = \dfrac{\dfrac{1-(1-f)^b}{f}}{(1-f)^b} = \dfrac{1}{f}\left(\dfrac{1}{(1-f)^b} - 1\right)$$

Answer

Substituting $b = 99$ and $f = 0.01$,

$$EV_{99} = \dfrac{1}{0.01}\left(\dfrac{1}{0.99^{99}} - 1\right) \approx 170 \text{ verses}$$

Extra Credit

Substituting $b = N$ and $f = \dfrac{1}{N}$,

$$\dfrac{K}{N} = \dfrac{EV_N}{N} = \lim_{N\to\infty} \dfrac{\dfrac{1}{\dfrac{1}{N}}\left(\dfrac{1}{\left(1-\dfrac{1}{N}\right)^{N}} - 1\right)}{N} $$

$$ = \lim_{N\to\infty} \left(\dfrac{1}{\left(1-\dfrac{1}{N}\right)^{N}} - 1\right) = \dfrac{1}{\dfrac{1}{e}}-1 = e-1$$

The graph below shows a sample of the relationship. When $P(\text{Forget}) = \frac{1}{\text{Verses}}$, $\frac{\text{Average Versus}}{\text{Verses}} \approx e-1$

Rohan Lewis

2023.02.06

Code can be found here.