Five Coins

You play a game with 5 coins. On turn 1 you flip all of them. On turn 2, you pick up all the ones that came up tails (leaving all the heads alone) and flip them again. You continue to do this until all the coins are heads. For example: 
Turn 1:  H T T H T
Turn 2:  - H T - H  (- means leave this coin alone)
Turn 3:  - - T - -
Turn 4:  - - T - -
Turn 5:  - - H - -
Done in 5 turns.
  1. As a reduced fraction, what is the expected number of turns you'll need to finish the game?
  2. As a reduced fraction, what is the probability you will finish the game in 3 turns or less?
  3. Can you find a general formula? If you have N coins to start, find the expected number of turns and the probability you will finish in k turns or less?
Larry Baum also suggests trying to solve for the general case: With N coins, probability p of getting heads on each flip, find the expected number of turns and the probability you will finish in k turns.

Source: Denis Borris, citing Larry Baum, citing The Price is Right.

Solutions were received from many people. (A few computer difficulties prohibit the easy cut-n-paste of their names and solutions. I will remedy this when I can.)
  1. 2470/651
  2. 16807/32768 = (7/8)^5
  3. For finishing in k turns, the probability is ( 1 - (1/2)^k )^N. I don't have a closed form for the expected number of turns. Samantha Levin proposed that if the above probability is F(k,N), then the probability of finishing in exactly k turns is f(k,N) = F(k,N) - F(k-1,N). And then the expected number would just be an infinite sum of k*f(k,N). I didn't get a nice simplification of that, yet.
I like Joseph DeVincentis' explanation of these solutions: 
The calculation of expected turns is recursive, so I'll start with one
coin and work backwards.

With one coin, with prob. 1/2 you will finish in one turn, and with prob.
1/2 you will still have one coin left after one turn.  If you let E(N)
be the expected number of turns to finish when starting with N coins, then
E(1) = 1/2 * 1 + 1/2 * (E(1)+1), so
1/2 * E(1) = 1, or
E(1) = 2.

With 2 coins, with prob. 1/4 you will finish in one turn, with prob. 1/2
you will have one coin left after one turn, and with prob. 1/4 you will
still have two coins left after one turn.  So:
E(2) = 1/4 * 1 + 1/2 * (E(1)+1) + 1/4 * (E(2)+1),
or, collecting the "one turn",
E(2) = 1 + 1/2 * E(1) + 1/4 ( E(2)
3/4 * E(2) = 1 + 1/2 * 2 = 2
E(2) = 8/3.

Similarly (but collecting "one turn" initially to simplify):

E(3) = 1 + 3/8 E(1) + 3/8 E(2) + 1/8 E(3)
7/8 E(3) = 1 + 3/4 + 1 = 11/4
E(3) = 22/7.

E(4) = 1 + 1/4 E(1) + 3/8 E(2) + 1/4 E(3) + 1/16 E(4)
15/16 E(4) = 1 + 1/2 + 1 + 11/14 = 46/14 = 23/7
E(4) = 368/105.

E(5) = 1 + 5/32 E(1) + 5/16 E(2) + 5/16 E(3) + 5/32 E(4) + 1/32 E(5)
31/32 E(5) = 1 + 5/16 + 5/6 + 110/112 + 23/42
           = (336 + 105 + 280 + 330 + 184)/336 = 1235/336
E(5) = 2470/651.

In general, E(N) = (2^N + sum[x=1..N-1]{C(N,x)*E(x)})/(2^N-1).

The probability of finishing the game in 3 turns or less is the
probability of each of 5 sets of 3 coin flips each containing at least
one head.  The probability of one such set of coin flips containing
a head is 7/8 (or 1-(1/2)^k for the generalized case of k flips).
The probability of all of them having a head is then (7/8)^5, or
(1-(1/2)^k)^N in the generalized case of N coins with k flips each.

This gives another method of solution for the expected number of
turns to win the game, in case you prefer an infinite sum over
a recursive formula.  E(N) = sum(x=1..inf){(1-(1/2)^x)^N}

If the probability of heads is p, then we can plug this directly into
the formula above.  The chance of at least one head in k flips of a
coin is 1-(1-p)^k, so the chance of finishing a game with N such coins
in k flips is (1-(1-p)^k)^N.
E(N,p) = sum(x=1..inf){(1-(1-p)^x)^N}
Mail to Ken