Sandbox

A coin puzzle

A coin problem
by Gary Antonik, Numberplay blog, New York Times, 17 March 2014

The post begins with this simple problem, posed by Daniel Finkel:

Consider this simple game: flip a fair coin twice. You win if you get two heads, and lose otherwise. It’s not hard to calculate that the chances of winning are 1/4… . Your challenge is to design a game, using only a fair coin, that you have a 1/3 chance of winning.

Continues "And here is my recipe for getting the most out of this problem: if you can solve it, do not stop with one answer. Rather, see how many answers you can come up with. I’ve posed this problem to many people, and I continue to hear novel solutions."

Here are three ways that quickly suggested themselves (I notice the these also turned up in readers' comments to the NYT!):

• Toss the coin until the first head appears. You win if this takes an even number of tosses
• Toss the coin twice. You win on HH and lose on HT or TH. If TT appears, ignore the result and make another two tosses.
• Toss the coin until the first appearance of HTT or HHT on consecutive tosses. You win HTT.

The third is an instance of the game Penney-Ante, invented by William Penney. It is a famous example of a non-transitive game: whatever triple the first player chooses, the second can choose a triple that has a better than even chance of coming up first. So if the you choose HTT, then second I will choose HHT, giving me a 2/3 chance of winning.

But I did not know, until searching for an online description of Penney-Ante, is that there is a variation with cards, called the Humble-Nishiyama Randomness Game. As described here

At the start of a game each player decides on their three colour sequence for the whole game. The cards are then turned over one at a time and placed in a line, until one of the chosen triples appears. The winning player takes the upturned cards, having won that "trick". The game continues with the rest of the unused cards, with players collecting tricks as their triples come up, until all the cards in the pack have been used. The winner of the game is the player that has won the most tricks.

In this scenario, the advantage of choosing second is even greater. For example, if the first player chooses BRR, the second should choose BBR. Now there is only a 5.18% that the first player wins, and 88.29% chance that the second player wins, and a 6.53% chance of a draw (a full table is available at the above link).

Discussion

Submitted by Bill Peterson