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, I have this problem about flipping coins and removing tails until all coins are gone. I need to find the expected number of rounds until the table is empty. Let me break it down step by step.

### Understanding the Problem
First, I need to understand the scenario:
1. **Initial Setup**: 3 fair coins on the table.
2. **Round Definition**: Flip all coins on the table. After flipping:
   - Remove coins that show tails.
   - Keep coins that show heads for the next round.
3. **Termination Condition**: The game ends when no coins are left on the table.

I need to find the expected number of rounds, R, until the table is empty.

### Approach
This seems like a problem involving expected value and recursion. I recall that for problems like this, it's often useful to define the expected value based on the current state and then break it down into simpler cases.

### Define Expected Value Function
Let's denote E(n) as the expected number of rounds needed to empty the table starting with n coins.

### Base Case
- **E(0)**: If there are no coins, the game is already over. So, E(0) = 0.

### Recursive Case
For n coins, in the first round:
1. Each coin is flipped independently.
2. The number of heads after the first flip follows a binomial distribution: k heads with probability C(n, k) * (1/2)^n, where k can range from 0 to n.

After the first round, the number of coins left is k (the number of heads). The expected number of additional rounds needed from this point is E(k).

But the first round itself counts as one round. So, the total expected number of rounds starting from n coins is:
E(n) = 1 + Σ [P(k heads) * E(k)] for k from 0 to n.

But P(k heads) is C(n, k) * (1/2)^n.

### Calculate E(1), E(2), E(3)
Since we start with 3 coins, we need to find E(3). But to find E(3), we need E(2), E(1), and E(0).

#### E(0)
As above, E(0) = 0.

#### E(1)
For n=1:
- Probability of 0 heads (tails): 1/2 → E(0) = 0
- Probability of 1 head (heads): 1/2 → E(1)

So, E(1) = 1 + (1/2)*E(0) + (1/2)*E(1)
But E(0) = 0, so:
E(1) = 1 + (1/2)*E(1)
Let's solve for E(1):
E(1) - (1/2)*E(1) = 1
(1/2)*E(1) = 1
E(1) = 2

#### E(2)
For n=2:
- Probability of 0 heads: 1/4 → E(0) = 0
- Probability of 1 head: 2/4 → E(1) = 2
- Probability of 2 heads: 1/4 → E(2)

So, E(2) = 1 + (1/4)*E(0) + (2/4)*E(1) + (1/4)*E(2)
Again, E(0) = 0, E(1) = 2:
E(2) = 1 + (2/4)*2 + (1/4)*E(2)
E(2) = 1 + 1 + (1/4)*E(2)
E(2) = 2 + (1/4)*E(2)
Subtract (1/4)*E(2) from both sides:
(3/4)*E(2) = 2
E(2) = 2 * (4/3) = 8/3

#### E(3)
For n=3:
- Probability of 0 heads: 1/8 → E(0) = 0
- Probability of 1 head: 3/8 → E(1) = 2
- Probability of 2 heads: 3/8 → E(2) = 8/3
- Probability of 3 heads: 1/8 → E(3)

So, E(3) = 1 + (1/8)*E(0) + (3/8)*E(1) + (3/8)*E(2) + (1/8)*E(3)
Again, E(0) = 0, E(1) = 2, E(2) = 8/3:
E(3) = 1 + (3/8)*2 + (3/8)*(8/3) + (1/8)*E(3)
Simplify the terms:
- (3/8)*2 = 6/8 = 3/4
- (3/8)*(8/3) = 24/24 = 1

So, E(3) = 1 + 3/4 + 1 + (1/8)*E(3)
Combine like terms:
E(3) = 2 + 3/4 + (1/8)*E(3)
E(3) = 11/4 + (1/8)*E(3)

Now, subtract (1/8)*E(3) from both sides:
(7/8)*E(3) = 11/4

Now, solve for E(3):
E(3) = (11/4) / (7/8) = (11/4) * (8/7) = 88/28 = 22/7

### Verification
Let me double-check my calculations to ensure accuracy.

#### Recalculating E(1)
E(1) = 1 + (1/2)*0 + (1/2)*E(1)
E(1) = 1 + (1/2)*E(1)
E(1) - (1/2)*E(1) = 1 → (1/2)*E(1) = 1 → E(1) = 2 ✔️

#### Recalculating E(2)
E(2) = 1 + (1/4)*0 + (2/4)*2 + (1/4)*E(2)
E(2) = 1 + 1 + (1/4)*E(2) → E(2) = 2 + (1/4)*E(2)
(3/4)*E(2) = 2 → E(2) = 8/3 ✔️

#### Recalculating E(3)
E(3) = 1 + (3/8)*2 + (3/8)*(8/3) + (1/8)*E(3)
= 1 + 6/8 + 24/24 + (1/8)*E(3)
= 1 + 3/4 + 1 + (1/8)*E(3)
= 2 + 3/4 + (1/8)*E(3)
= 11/4 + (1/8)*E(3)
(7/8)*E(3) = 11/4 → E(3) = 22/7 ✔️

### Conclusion
The expected number of rounds until the table is empty, starting with 3 coins, is 22/7.

\boxed{\dfrac{22}{7}}