Two prisoners, a chessboard, 64 coins and one secret square. Can a single flipped coin always reveal which square was chosen?
Two prisoners, 64 coins and a secret square
Riddle statement
Two prisoners are allowed to agree on a strategy beforehand.
Then the first prisoner enters a room with a chessboard. On each of the 64 squares there is one coin, showing either heads or tails. The guard secretly designates one square as the target.
The first prisoner may flip exactly one coin, then leaves.
The second prisoner then enters, sees the resulting board, and must identify the target square.
Can the prisoners choose a strategy that always works?
Show solution
Solution
Answer: yes.
Number the 64 squares from 0 to 63. The prisoners agree that a heads-up coin contributes its square number, while a tails-up coin contributes nothing.
The first prisoner looks at all the heads-up coins and computes the XOR of their square numbers. Call this value S.
If the secret square has number T, the first prisoner flips the coin on square
Why does this work? Flipping a coin on square k toggles whether k is included in the total XOR. So the new XOR becomes the old XOR with k applied.
Here k = S \oplus T, so the new XOR is
The second prisoner enters, computes the XOR of the square numbers with heads-up coins, and obtains T. That number identifies the secret square.