Fog Creek Software
Discussion Board




pennies

Old solution is listed below.

In the case of 'HHT', O would win at the 2nd turn,
and this round is over. So each wins 3 times, the game is fair.



Solved by blah on November 14, 2001

solution: pennies

(ummm,, I don't right too good. ;) )

In a 3 turn game:

O needs HH, X needs HT

HHH O

HHT OX

HTH X

HTT X

THH O

THT X

TTH

TTT

X wins 4 times out of 8, O wins 3 times out of 8

Its because in the event X loses there is a 50% chance of starting out on another H where O has to start on a T 75% of the time. (or something like that...)

Pan, Wenyu
Friday, December 13, 2002

Wenyu

In any game each player has a separate sequence of coin tosses.

Call getting the sequence right a 'hit'. Getting a 'hit' before your opponent results in a win. Getting one at the same time results in a tie.

There are two sequences that give X a 'hit' on the second toss, and two that give O a hit. There is an additional one that gives  O a hit on the third toss, and two that give X a hit on the third toss. So at any point in the game X has a higher probability of getting a 'hit' by that point, and so will win in the long run.

David Clayworth
Friday, December 13, 2002

David,

You said the other day: 'when the HT guy loses, he is set up to get a win next toss. The HH guy cannot win next toss.'

That is correct. But you forgot this : when the HH guy wins, he is set up to get a win next toss. The HT guy cannot win next toss.

So consider the 1st senario HHH O, it should be HHH OO if the 2nd can be counted as HHT OX. Still, the game is fair.

Pan, Wenyu
Monday, December 16, 2002

My understanding was that when a win occurred the game stopped. If another game then takes place it starts from scratch.

David Clayworth
Monday, December 16, 2002

Hmm, I was slightly premature in my previous reply. I also assumed that if both players 'hit' a tie occurs, and the game restarts. In which has the case 'HHH' cannot occur for O.

If we assume that in the case of a tie the game continues, we have a more complex situation. Let us analyse the possible states after two throws. O needs HH and X needs HT

1) O hits and X misses. O wins. Game over. Probability 25%*75%=18.75%

2) X hits and O misses. X wins. Game over. Probability as above

3) Both miss. Game continues. Probability 75%*75%=56.25%

4) Both hit. Game continues Probability 6.25%

In case 3, O might have thrown HT,TH or TT with equal probability. X might have thrown HH,TT or TH with equal probability.

In case 4 we know that O has HH and X has HT.

In the throw after case 3, X has a 50% chance of a hit for two of the possible three combinations he has. O has a 50% chance  of a hit for only one of his three possible combinations. Probability of a hit is:

O: 50% * 33% * 56.25% ~ 9%
X: 50% * 66% * 56.25% ~ 19%

Considering case 4, only O can hit with a 50% chance.
Probability of a hit is

O: 50% * 6.25% ~ 3%

So O has approximately a 12% chance of a hit on (exactly) the third throw, and X has a 19% chance. Which is closer to fair than the case where the game restarts after a tie, but still not fair. X will win in the long run.

One way of looking at this is to notice that in this case HHH is a valid 3rd round hit for O (which it isn't in the restart case) but ONLY in the somewhat unlikely case that X throws HT. All of X's third round hit combinations are valid in every case except the one where O wins on throw 2

David Clayworth
Monday, December 16, 2002

David,

You're correct. If the game stops after a win and continues after a tie, X has the advantage.

Pan, Wenyu
Monday, December 16, 2002

I see that this discussion has been silent for a while....  Since this is a forum for "tech" interview questions, I say write a Monte Carlo simulation!  Pretty easy to do, and if I did it right, it reveals that the game is fair, whether or not you keep playing on ties.

nojo
Wednesday, January 07, 2004

*  Recent Topics

*  Fog Creek Home