[psyang]

Originally Posted by You Need a Thneed

I’m still mystified by this puzzle:

Two people are in prison, and the jailer offers them a math puzzle, which if they give the right answer, the jailer will let them go free, if they give the wrong answer, they will be executed.

- the prisoners know all of the rules of the game beforehand and can discuss their strategy before the puzzle starts.

- there is a chess board, and 64 coins, one for each space. There is also a token that can completely hide under a coin without being able to tell if it’s there.

- after the prisons discuss their strategy, the jailer sends one of them out of the room, no communication is possible between the two prisoners.

- with only the jailer and one prisoner in the room, the jailer places one coin on each space of the chess board, head or tails in each space, jailers choice.

- the jailer places the token under one coin, with the prisoner aware of where the coin is placed.

- The prisoner can flip any ONE and only one coin from heads to tails or vice versa.

- there is no heat transfer, to tell if one coin is warmer than others.

- After the coin is flipped, the second prisoner returns to the cell, and has ONE choice to pick up a coin to see if the token is underneath. If they pick up the coin with the token under, they go free, if not, they are executed.

- how do the prisoners survive?

I haven't heard this problem before, but my initial instinct is it is a parity problem, and probably closely related to hamming codes. I'll try to take some time this weekend to work it out.