Fog Creek Software
Discussion Board


I never get these right, but...

I don't buy the solution.

The puzzle was presented as "the game continues until someone wins".  The solution presents a "3-turn game", and examines all eight outcomes.  The second outcome, HHT, is presented as both players win.  But (it seems to me) the game is over after the second toss, so the 'HT' player does not garner credit, and the overall results are 3/3, not 4/3.

Now, if the game were presented as "the pennies are flipped some arbitrary number of times and player with the most occurrences of his sequence wins", then I would have no gripe.

Monday, August 16, 2004

Well, I see your point and I agree on it.
But when I look at the solution from a common sense point of view, it does make sense.

I think of it like this:
The guy trying to get HH may sometimes get tails, when he does he has to start over again and get 2 consecutive heads. So a wrong flip for him means he starts over and needs at least 2 more tosses.

While the other guy trying to get HT will always either get heads so he's half way there, or T after an H so he already won. In other words, if he gets a wrong H it can act as the start of an HT and he'd only need one more toss with a T to win.

Christian Kamel
Wednesday, August 18, 2004

I wrote a simulation; with 100,000 tries, the results are:

awins:  18544 (18.54%)
bwins:  18723 (18.72%)
tie:          6232 ( 6.23%)
none:  56501 (56.50%)

(a wins if he rolls HH, b wins if she rolls HT)

The odds look even to me.

Friday, August 20, 2004

Christian's rationale is easy to visualize with a state diagram for each player:

      T            H               
    /  \        /    \
    v  /        v    /
A: (0)-- H -->(1)-- T -->(WIN)

    /  \
    v  /
B: (0)-- H -->(1)-- H -->(WIN)
    ^            /
      \          /
        -- T --

Each represents a binary Markov source that generates H/T sequences; A's end in HT and B's end in HH. Since each state transition has a probability of 1/2, intuition suggests that A's sequences will be shorter, on average, than 'B's.

This means that 'A' will, on average, reach the winning end state first, which gives player 'A' the advantage.

Note: intuition could be wrong, so we should calculate each source's average sequence length to verify the conclusion.

Chuck Boyer
Sunday, August 22, 2004

Sorry about the lousy diagrams.  ASCII art doesn't look so good with a variable pitch font. :/

Chuck Boyer
Sunday, August 22, 2004

The solution is wrong.  Both players are equally likely to win.

Both strategies require a heads on the previous flip to have a chance to win on the next flip.  Since the next flip is equally likely to be heads or tails, both strategies are equivalent.

Of course, if we are flipping coins and scoring continuously, HHH has to count as two wins; if you have to "start over" every time you win, the two-heads strategy is at a disadvantage.  This seems to be where the confusion is coming from.

Paul N
Tuesday, October 5, 2004

*  Recent Topics

*  Fog Creek Home