Home > Riddles > Two prisoners, 64 coins and a secret pocket

Two prisoners, 64 coins and a secret pocket

Visual trapsLevel 4 · Advanced · ●●●●○

There are two prisoners and a guard. The guard has a $8\times 8$ chess board and a coin on each square (64 in total), each one heads or tails.

Challenge rules:

  1. The guard sets up the board with random orientations.
  1. The first prisoner enters.
  1. The guard points to a secret square that only the first prisoner sees.
  1. The first prisoner can flip at most one coin and leaves.
  1. The second prisoner enters, sees the final board and must identify the secret square.

If he gets it right, both are free. What is the strategy that guarantees success?

Hints

Show hints
  1. Let T be the secret index marked by the guard.
  2. Defines one bit per square: heads =1, tails =0.
  3. Yes, you always can. The universal strategy is to encode the secret slot with XOR over $0,\dots,63$ indices.

Solution

Show full solution

Answer: Yes, you can always. The universal strategy is to encode the secret slot with XOR over $0,\dots,63$ indices.
1) Board Coding

  • Number the 64 squares as $0,1,\dots,63$.
  • Defines one bit per square: heads $=1$, tails $=0$.
  • Let $T$ be the secret index marked by the guard.

Calculate the XOR of all face squares:

$$ X=\bigoplus_{i:\,b_i=1} i. $$

2) Which coin to flip
The first prisoner calculates:

$$ F=X\oplus T. $$

  • If $F=0$, no need to flip any (allowed: at most one).
  • If $F\neq0$, exactly flip the coin from square $F$.

3) Correction test
Flipping $F$ changes the global XOR on $\oplus F$, then the second prisoner sees:

$$ X'=X\oplus F. $$

Replacing:

$$ X'=X\oplus(X\oplus T)=(X\oplus X)\oplus T=T. $$

Therefore, the final XOR read by the second prisoner is exactly the secret index.
4) Complete example
If the faces are in $\{2,5,9,12\}$, then:

$$ X=2\oplus5\oplus9\oplus12=2. $$

If the guard dials $T=11$:

$$ F=2\oplus11=9. $$

Square 9 is flipped and the final XOR becomes 11, which identifies the secret square.
5) Methodological readingThe trick does not depend on the initial state: the first prisoner sends 6 bits of information (index 0..63) through a single controlled inversion. This guarantees success in all cases.

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 →