Using your Head is Permitted

September 2015 riddle

UPDATE (7 September): In answer to a question asked by several readers: to solve, you need to come up with a strategy that ensures the highest success probability attained by any of the possible strategies. You are not, however, required to prove its maximality.

The following riddle comes from Omer Angel. (Thanks, Omer!)

A warden sets a (two sided) coin on each square of a chess board in arbitrary random configuration ({heads,tails}64).

Prisoner A is taken to the board. The warden hides a piece of paper under one of the coins, and the prisoner sees which coin it is. The prisoner is asked to flip one of the coins on the board (where the prisoner chooses the coin), and is then taken away.

Prisoner B is taken to the room, and is asked to identify which coin hides the paper. (Prisoner B does not need to identify which coin was flipped by A.) If successful, the two are released.

Is there a strategy (that Prisoner A and Prisoner B can agree on in advance) that will allow Prisoner A to communicate to B with high probability where the paper is hidden?

Please help the two prisoners and come up with such a strategy, while Omer and I debate the question of whether this experiment would pass an ethics review board.

List of solvers:

Yuzhou Gu (1 September 10:54)
Oded Margalit (1 September 14:35)
Guangda Huzhang (1 September 18:21)
Daniel Bitin (2 September 22:08)
Shunyu Yao (3 September 01:02)
Harald Bögeholz (3 September 04:32)
Samuel Tang (3 September 20:08)
Jim Boyce (4 September 12:28)
Mike Liardet (9 September 02:48)
Austin Shapiro (10 September 02:24)
Dan Dima (12 September 00:13)
Itsik Horovitz (13 September 16:35)
Radu-Alexandru Todor (14 September 07:17)
Jan Fricke (14 September 23:47)
Julien Berestycki (15 September 23:02)
Jiang Qiaochu (16 September 22:57)
Liu Yi (29 September 22:04)

Elegant and original solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page