math-prob-01

# The Vanishing Coins

You start with **3 fair coins** on the table.

A **round** consists of flipping every coin that is currently on the table (all at once). After the flips, remove every coin that landed **tails**; every coin that landed **heads** stays on the table for the next round. You then play another round with whatever coins remain.

The game ends at the moment the table is empty (no coins remain).

Let $R$ be the number of rounds played until the table is empty. Compute the expected value $\mathbb{E}[R]$.

Give your answer as an exact fraction in lowest terms, written as `a/b` (for example, `7/3`).

I need to find the expected number of rounds until all coins are eliminated.

Let me define $E_n$ as the expected number of rounds starting with $n$ coins.

I want to find $E_3$.

First, let me establish the base cases:
- $E_0 = 0$ (no coins means no rounds)
- $E_1 = 1 + \frac{1}{2}E_0 + \frac{1}{2}E_1 = 1 + \frac{1}{2} \cdot 0 + \frac{1}{2}E_1 = 1 + \frac{1}{2}E_1$

Solving for $E_1$:
$E_1 = 1 + \frac{1}{2}E_1$
$\frac{1}{2}E_1 = 1$
$E_1 = 2$

Now for $E_2$:
Starting with 2 coins, after one round:
- Both coins land heads (probability $\frac{1}{4}$): 2 coins remain, so expected rounds is $1 + E_2$
- One coin lands heads, one tails (probability $\frac{1}{2}$): 1 coin remains, so expected rounds is $1 + E_1$
- Both coins land tails (probability $\frac{1}{4}$): 0 coins remain, so expected rounds is $1 + E_0 = 1$

$E_2 = 1 + \frac{1}{4}E_2 + \frac{1}{2}E_1 + \frac{1}{4} \cdot 0$
$E_2 = 1 + \frac{1}{4}E_2 + \frac{1}{2} \cdot 2 + 0$
$E_2 = 1 + \frac{1}{4}E_2 + 1$
$E_2 = 2 + \frac{1}{4}E_2$
$\frac{3}{4}E_2 = 2$
$E_2 = \frac{8}{3}$

Now for $E_3$:
Starting with 3 coins, after one round:
- All 3 coins land heads (probability $\frac{1}{8}$): 3 coins remain, so expected rounds is $1 + E_3$
- Exactly 2 coins land heads, 1 tails (probability $\frac{3}{8}$): 2 coins remain, so expected rounds is $1 + E_2$
- Exactly 1 coin lands heads, 2 tails (probability $\frac{3}{8}$): 1 coin remains, so expected rounds is $1 + E_1$
- All 3 coins land tails (probability $\frac{1}{8}$): 0 coins remain, so expected rounds is $1 + E_0 = 1$

$E_3 = 1 + \frac{1}{8}E_3 + \frac{3}{8}E_2 + \frac{3}{8}E_1 + \frac{1}{8} \cdot 0$
$E_3 = 1 + \frac{1}{8}E_3 + \frac{3}{8} \cdot \frac{8}{3} + \frac{3}{8} \cdot 2 + 0$
$E_3 = 1 + \frac{1}{8}E_3 + 1 + \frac{3}{4}$
$E_3 = 2 + \frac{3}{4} + \frac{1}{8}E_3$
$E_3 = \frac{11}{4} + \frac{1}{8}E_3$
$\frac{7}{8}E_3 = \frac{11}{4}$
$E_3 = \frac{11}{4} \cdot \frac{8}{7} = \frac{22}{7}$

Let me verify this is correct by checking the pattern.

Actually, let me reconsider the problem more systematically.

For $E_n$, in one round:
- Probability $\binom{n}{k} \left(\frac{1}{2}\right)^n$ that exactly $k$ coins land heads
- If $k$ coins land heads, we continue with $k$ coins for the remaining rounds

So: $E_n = 1 + \sum_{k=0}^{n} \binom{n}{k} \left(\frac{1}{2}\right)^n E_k$

This gives us:
$E_0 = 0$
$E_1 = 1 + \frac{1}{2}E_1 + \frac{1}{2}E_0 = 1 + \frac{1}{2}E_1$
So $E_1 = 2$

$E_2 = 1 + \frac{1}{4}E_2 + \frac{1}{2}E_1 + \frac{1}{4}E_0 = 1 + \frac{1}{4}E_2 + \frac{1}{2}(2) + 0 = 2 + \frac{1}{4}E_2$
So $E_2 = \frac{8}{3}$

$E_3 = 1 + \frac{1}{8}E_3 + \frac{3}{8}E_2 + \frac{3}{8}E_1 + \frac{1}{8}E_0$
$E_3 = 1 + \frac{1}{8}E_3 + \frac{3}{8} \cdot \frac{8}{3} + \frac{3}{8} \cdot 2 + 0$
$E_3 = 1 + \frac{1}{8}E_3 + 1 + \frac{3}{4}$
$E_3 = \frac{11}{4} + \frac{1}{8}E_3$
$\frac{7}{8}E_3 = \frac{11}{4}$
$E_3 = \frac{11}{4} \cdot \frac{8}{7} = \frac{22}{7}$

Therefore, $\mathbb{E}[R] = \boxed{\frac{22}{7}}$.