Solution to "Penney's Game" *LINK*

Alex Y
This three coin flip problem was developed in 1969 by Walter Penney.

The solution is easy to implement, but very difficult (IMO) to understand its workings:

If A chooses F1, F2, F3 as his sequence, B should choose ~F2, F1, F2, where ~F2 is the opposite of F2. So, for instance if A selects HTT, B should choose H(the opposite of A's second pick)HT.

Interestingly, this strategy works no matter the length of sequences you are comparing. So if you are comparing sequences of 10 flips, once A has chosen his sequence, B should choose the opposite of A's second flip followed by A's first 9 choices.

Now here is a really weird result, applying this rule:
HHT is likely to come up before HTT
THH is likely to come up before HHT
TTH is likely to come up before THH
HTT is likely to come up before TTH

So if you toss a coin multiple times, which of these four patterns is likely to come up first, since each of them (if you believe the rule) has another that is likely to come up before it? This is so counter-intuitive that it makes one believe that this rule must be wrong (it's not).

Another weird thing about this game is that if you figure out the expected number of flips before a certain sequence comes up, getting this expected time for two different sequences may NOT tell you which is likely to come up first.

The Wiki article on Penney's Game has more info, but the PDF at this link has all the math you could ever want on this puzzle:

© 1998 - 2017 by Ellis Walentine. All rights reserved.
No parts of this web site may be reproduced in any form or by
any means without the written permission of the publisher.