Fog Creek Software
Discussion Board

Answer to "Pennies" Riddle Flawed.

A slight flaw in the answer to this riddle. 

HTT    X

O wins if H, then H
X wins if H, then T

Therefore, O wins 3/8 of the time, and X wins 4/8 of the time, right.....?  Nope!  In the HHT case O already won before the third flip happened.  They can never both win on any given flip.  So, the game IS fair and each person has a 3/8 chance of winning.  WRONG again.  Each person has a 1/2 chance of winning!  Maybe our intuition and grade school math skills should have lead us to this conclusion.  Check out the two "tie" cases.  Since we keep flipping until there is a winner, we cannot simply stop on the third flip with these bottom two cases.  So we flip again:


This flip still yields a 1/2 chance of winning.  Then that "tie" case must be determined.... sounds kinda like induction (dare I mention it).  Each flip, the game has a higher probability of yielding a winner.  The probability that the game winner is not determined after a given flip k is 2/2^k.  Notice that k must begin at 1.  So 2/2^1 = 1, or 100% of the time there will be no winner after the first flip, which makes intuitive sense. 

Hope this provides some insight that over time [unchanged]intuition will trump deviant thinking... or something like that

Eric Ott
Thursday, February 20, 2003

There is a flaw in the stated answer, but your analysis is also flawed.  Each person flips his own penny.  Therefore, both people can win at once.  The game ends once one or both people win on the same flip (I assume, otherwise it turns out fair).

I will attempt to demonstrate who wins
Player Y needs HH to win
Player M needs HT to win

Let G(n) be the probability that the game lasts at least n flips.

Let P(n,Y) be the probability that Y wins on flip n, given that that many flips occur, let P(n,M) be the probability the M wins under the same circumstances.

P(1,Y) = P(1,M) = 0
must have 2 flips for anyone to win

P(2,Y) = P(2,M) = 1/4
HH equally likely as HT

for x > 2

P(x,Y) = 1/3 * 1/2 = 1/6
since Y did not win on flip x-1, flips x-2 and x-1 were HT, TH, and TT with equal probability.  So flip x-1 was
H with probability 1/3

P(x,M) = 2/3 * 1/2 = 1/3
flips x-2 and x-1 were HH, TH, TT with equal probability, so flip x-1 was H with probability 2/3

This, by the way, is a rough proof already that M will win more often, since on any given flip he is at least as likely
to win.  In an interview, I'm guessing it would stop here

But let's finish it.
G(2) = 1  ; must reach two flips
G(3) = 1 - 1/4 - 1/4 + 1/16 = 9/16

for x > 3
G(x) is the odds that the game gets to x-1 flips and does not stop there

G(x) = G(x-1) * C(x-1)

where C(y) is the odds that it does not stop at y-1 flips given that it has gotten there

C(y) = 1 - P(y,Y) - P(y,M) + P(y,Y)*P(y,M)
C(y) = 1 - 1/6 - 1/3 + 1/18 = 10/18
since both can win at once, don't double count

G(x) = G(x-1) * 10/18 for x > 3

So the probability of Y winning is
1/4 + 1/6*9/16 + 1/6*9/16*10/18 +          1/6*9/16*10/18*10/18 + ...

The probability of M winning is
1/4 + 1/3*9/16 + 1/3*9/16*10/18 + 1/3*9/16*10/18*10/18 + ...

solving the infinite seires using:
1+10/18+10/18*10/18 + ... = 18/8


Probability of Y winning
1/4 + 1/6*9/16*18/8 = 192/768 + 162/768 = 354/768 ~= .46

Probability of M winning
1/4 + 1/3*9/16*18/8 = 192/768 + 384/768 = 576/768 = .75

Note that since both can win at once, the sum of the probabilities is > 1.

I believe I managed to get all the math right, but it's kinda early in the morning/late at night [when I first did this, I've just copied it from an earlier thread] so please point out any errors.

Roy Pollock
Friday, February 21, 2003

*  Recent Topics

*  Fog Creek Home