Home > Riddles > Two prisoners, 64 coins and a escaque secreto

Two prisoners, 64 coins and a escaque secreto

Master playsLevel 4/5

Everything seems insufficient: a single coin exchanged to mark a box between sixty and four. The surprise is that the message is not in a specific currency, but in the parity of the entire board.

There are two prisoners and a guard. On a chess board there is a coin in each square, showing heads or tails.

Before starting, the prisoners can agree on a strategy. Then the first prisoner enters.

The guard points out a secret box. The first prisoner can flip exactly one coin, whichever one he wants, and then he leaves.

The second prisoner then enters, who sees the resulting board but does not know which square the guard pointed to. Can you agree on a strategy so that the second prisoner always identifies the secret box?

Hints

Show hints
  1. Number the 64 boxes from 0 to 63.
  2. Think of each number as a 6-bit string.
  3. Usa the xor of the indices of the coins that muestran head.

Solution

Show full solution

Answer: yes. They can use a special binary addition, called xor, to convert the entire board into a number from 0 to 63. First they number the boxes from 0 to 63. Before entering, they agree that a heads coin counts and a tails coin does not count. The first prisoner looks at all the coins that are heads and calculates the xor of their indices. Call it $S$. If the secret box has number $T$, the first prisoner must flip the coin from the box: $$
S\oplus T.
$$ Why does it work? When you flip a coin, its index enters or exits the total xor. In both cases, the new xor of the board becomes exactly $T$. Then the second prisoner enters, calculates the xor of the indices of the coins that are heads and obtains $T$. That number tells you which was the secret box.

Related riddles

Keep practicing

If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.

← Previous: The three prisoners and the red hats · Next: The two ropes →