   pennies - problem with solution I would argue that the odds would be 50-50 because the game is not on a fixed turn basis. In a 3 turn game: O needs HH, X needs HT HHH OO  *added O HHT OX HTH X HTT X THH O THT X TTH TTT After realizing that HHH would actually produce 2 winning combinations, the counts turn out to be 4X and 4O. Taking it to a 4 round game: HHHH OOO HHHT OOX HHTH OX HHTT OX HTHH OX HTHT XX HTTH X HTTT X THHH OO THHT OX THTH X THTT X TTHH O TTHT X TTTH TTTT The result are 12X and 12O - an even 50-50 split Jacob Thursday, February 7, 2002 I think this has already been covered: http://discuss.fogcreek.com/techinterview/default.asp?cmd=show&ixPost=144&ixReplies=22 Michael H. Pryor Thursday, February 7, 2002 The above thread refers to the "Painfully Easy" problem, not to this, the "Pennies" problem. Joseph, it looks like you're assuming the game continues indefinitely, with each player accumulating wins.  That makes the game fair.  However, the problem said the game wasn't fair, so I think the game ends once one or both people win on the same flip. 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 gives: 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 so please point out any errors. Roy Pollock Friday, February 8, 2002 Yes it has, but since this topic no longer appears on the message board, I am going to reply here. To make sure, I am responding to post 39 - pennies - posted May 14, 2001. After reading the entire archive, it seems as though the posters are not solving the problem being asked.  The problem does not state 'If I told you that one of the pennies was a head, what is the probability that the second is also came up heads'. The problem was stated as a game in which player 1 (p1) needed to get HT is order to win and p2 needed to get HH to win.  After someone had hit their expected target, the game would end and no more tosses would take place.  so after 2 tosses, the results are as follows. HH p2 wins HT p1 wins TH continue TT continue After 3 tosses, then results are HHH p2 wins HHT p1 & p2 wins HTH p2 wins HTT p2 wins THH p1 wins THT p2 wins TTH continue TTT continue After looking at this, it seems as though p1 would have the advantage as demonstrated in the answer given.  But what is not accounted for is the fact that HHH would result in p2 winning twice (which would not be allowed since the game would end after the second flip).  The fact that I have had 3 straight heads on coin flips does not mean that the next flip of the coin will result in a tails.  Granted, the odds of 4 straight heads is 1/16 but the odds that the next flip will be heads is 1/2. Unless you are using a two-headed coin :) Jacob Friday, February 8, 2002 Recent Topics Fog Creek Home