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

Alright, let's tackle this problem step by step. I'm going to think about how the game progresses with the coins and try to find the expected number of rounds until all coins are removed.

### Understanding the Problem

We start with 3 fair coins on the table. A round consists of:
1. Flipping all currently on-table coins simultaneously.
2. After flipping, any coin that shows tails is removed from the table.
3. Coins that show heads stay on the table for the next round.
4. The game ends when no coins are left on the table.

We need to find the expected number of rounds, \( \mathbb{E}[R] \), until the table is empty.

### Breaking Down the Problem

First, let's think about what happens in one round with a certain number of coins. 

- **Initial state**: 3 coins.
- After flipping:
  - Each coin independently has a 1/2 chance of being heads (stays) and 1/2 chance of being tails (removed).
  
So, after one round:
- Number of coins that stay is the number of heads in the flip, which is a binomial random variable with parameters \( n = 3 \) and \( p = 1/2 \).

The possible outcomes after the first round are:
- 0 heads: all 3 coins are tails → table empty after 1 round.
- 1 head: 2 coins removed, 1 stays → next round with 1 coin.
- 2 heads: 1 coin removed, 2 stay → next round with 2 coins.
- 3 heads: 0 coins removed, 3 stay → next round with 3 coins.

### Expected Number of Rounds

Let's denote \( \mathbb{E}[R] \) as the expected number of rounds starting with 3 coins. Similarly, let's define:
- \( \mathbb{E}[R_n] \) as the expected number of rounds starting with \( n \) coins.

Our goal is to find \( \mathbb{E}[R_3] \).

#### Base Case

- \( \mathbb{E}[R_0] = 0 \): If there are no coins, no rounds are needed.

#### Recursive Relation

For \( n \geq 1 \), after one round with \( n \) coins:
- Each coin independently has a 1/2 chance of being tails (removed) and 1/2 chance of being heads (stays).
- The number of coins that stay is \( k \), where \( k \) follows a binomial distribution \( \text{Binomial}(n, 1/2) \).
  
The expected number of rounds starting with \( n \) coins is:
\[ \mathbb{E}[R_n] = 1 + \sum_{k=0}^{n} P(k \text{ coins stay}) \cdot \mathbb{E}[R_k] \]
\[ \mathbb{E}[R_n] = 1 + \sum_{k=0}^{n} \binom{n}{k} \left(\frac{1}{2}\right)^n \mathbb{E}[R_k] \]

This is because after one round, we've used one round, and then we have \( k \) coins left, which will take \( \mathbb{E}[R_k] \) more rounds on average.

#### Calculating \( \mathbb{E}[R_n] \) for Small \( n \)

Let's compute \( \mathbb{E}[R_n] \) for \( n = 0, 1, 2, 3 \).

1. \( \mathbb{E}[R_0] = 0 \).

2. \( \mathbb{E}[R_1] \):
   - After one round with 1 coin:
     - 0 heads (tails): 1/2 chance → table empty after 1 round.
     - 1 head: 1/2 chance → next round with 1 coin.
   - So:
     \[ \mathbb{E}[R_1] = 1 + \frac{1}{2} \cdot \mathbb{E}[R_0] + \frac{1}{2} \cdot \mathbb{E}[R_1] \]
     \[ \mathbb{E}[R_1] = 1 + \frac{1}{2} \cdot 0 + \frac{1}{2} \cdot \mathbb{E}[R_1] \]
     \[ \mathbb{E}[R_1] - \frac{1}{2} \mathbb{E}[R_1] = 1 \]
     \[ \frac{1}{2} \mathbb{E}[R_1] = 1 \]
     \[ \mathbb{E}[R_1] = 2 \]

3. \( \mathbb{E}[R_2] \):
   - After one round with 2 coins:
     - 0 heads: \( \binom{2}{0} (1/2)^2 = 1/4 \) → table empty after 1 round.
     - 1 head: \( \binom{2}{1} (1/2)^2 = 2/4 = 1/2 \) → next round with 1 coin.
     - 2 heads: \( \binom{2}{2} (1/2)^2 = 1/4 \) → next round with 2 coins.
   - So:
     \[ \mathbb{E}[R_2] = 1 + \frac{1}{4} \cdot \mathbb{E}[R_0] + \frac{1}{2} \cdot \mathbb{E}[R_1] + \frac{1}{4} \cdot \mathbb{E}[R_2] \]
     \[ \mathbb{E}[R_2] = 1 + \frac{1}{4} \cdot 0 + \frac{1}{2} \cdot 2 + \frac{1}{4} \cdot \mathbb{E}[R_2] \]
     \[ \mathbb{E}[R_2] = 1 + 1 + \frac{1}{4} \mathbb{E}[R_2] \]
     \[ \mathbb{E}[R_2] - \frac{1}{4} \mathbb{E}[R_2] = 2 \]
     \[ \frac{3}{4} \mathbb{E}[R_2] = 2 \]
     \[ \mathbb{E}[R_2] = \frac{8}{3} \]

4. \( \mathbb{E}[R_3] \):
   - After one round with 3 coins:
     - 0 heads: \( \binom{3}{0} (1/2)^3 = 1/8 \) → table em