Riddler Classic

By Zach Wissner-Gross

From Gary Yane comes a question that launched a million flips:

I have in my possession 1 million fair coins. Before you ask, these are not legal tender. Among these, I want to find the “luckiest” coin.

I first flip all 1 million coins simultaneously (I’m great at multitasking like that), discarding any coins that come up tails. I flip all the coins that come up heads a second time, and I again discard any of these coins that come up tails. I repeat this process, over and over again. If at any point I am left with one coin, I declare that to be the “luckiest” coin.

But getting to one coin is no sure thing. For example, I might find myself with two coins, flip both of them and have both come up tails. Then I would have zero coins, never having had exactly one coin.

What is the probability that I will — at some point — have exactly one “luckiest” coin?

My Solution

flip_coins <- function () {
  coins_left = 1000000
  while (coins_left > 1) {
    coins_left <- rbinom(1, coins_left, 0.5)
  }
  return(coins_left)
}

lucky_coins <- 0
for (i in 1:10000) {
  lucky_coins <- lucky_coins + flip_coins()
}

print(lucky_coins/10000)
## [1] 0.7201

Now that we have an answer as a sort of security blanket, let’s try to find an exact solution by considering lower numbers of coins:

with two coins:

  1. 2 tails (\(\frac{2 \choose 2}{2^2} = \frac{1}{4}\)): we have no luckiest coin
  2. 1 tail + 1 head (\(\frac{2 \choose 1}{2^2} = \frac{1}{2}\)): we have a luckiest coin
  3. 2 heads (\(\frac{2 \choose 2}{2^2} = \frac{1}{2}\)): we try again

with three coins:

  1. 3 tails (\(\frac{3 \choose 3}{2^3} = \frac{1}{8}\)): we have no luckiest coin
  2. 2 tails + 1 head (\(\frac{3 \choose 2}{2^3} = \frac{3}{8}\)): we have a luckiest coin
  3. 2 heads + 1 tail (\(\frac{3 \choose 2}{2^3} = \frac{3}{8}\)): this reduces to the two coin situation
  4. 3 heads (\(\frac{3 \choose 3}{2^3} = \frac{1}{8}\)): we try again

with four coins:

  1. 4 tails (\(\frac{4 \choose 4}{2^4} = \frac{1}{16}\)): we have no luckiest coin
  2. 3 tails + 1 head (\(\frac{4 \choose 3}{2^4} = \frac{1}{4}\)): we have a luckiest coin
  3. 2 tails + 2 heads (\(\frac{4 \choose 2}{2^4} = \frac{3}{8}\)): this reduces to the two coin situation
  4. 3 heads + 1 tail (\(\frac{4 \choose 3}{2^4} = \frac{1}{4}\)): this reduces to the three coin situation
  5. 4 heads (\(\frac{4 \choose 4}{2^4} = \frac{1}{16}\)): we try again

Generally, it seems that when we have \(n\) coins, the probability of getting a luckiest coin

\[ f(n) = \frac{n \choose n-1}{2^n} + \frac{n \choose n-2}{2^n} \cdot f(n-1) + \frac{n \choose n-3}{2^n} \cdot f(n-2) + \cdots + \frac{n \choose 2}{2^n} \cdot f(2) \]

This seems like a math sort of thing but I got a 1 on the AP Calculus B/C test in my senior year of high school, so I wouldn’t know! I also can’t solve this numerically without doing some math trick first because:

print(2^1000000)
## [1] Inf