We flip $n$ fair coins every iteration of the game. Every coin that shows heads is removed from the game and we use the remaining $n-k$ coins to play the game again (where $k$ is the number of heads in that iteration). What is the expected number of iterations we need to complete before all the coins are gone.
[Math] Expected number of coin tosses needed until all coins show heads
combinatoricsprobabilityprobability theory
Best Answer
Hint: After $m$ flips, the chance that a given coin has been removed is $1-2^{-m}$. The chance that all the coins have been removed is then $(1-2^{-m})^n$. The chance the last coin is removed on flip $m$ is then $(1-2^{-m})^n-(1-(1-2^{-m+1})^n)$ because it has to survive through flip $m-1$.