Dos prisioneros, 64 monedas y un escaque secreto

1. Numera las 64 casillas del 0 al 63.
2. Piensa en cada número como una cadena de 6 bits.
3. Usa el xor de los índices de las monedas que muestran cara.

Respuesta: sí. Pueden usar una suma binaria especial, llamada xor, para convertir todo el tablero en un número del 0 al 63.

Primero numeran las casillas del 0 al 63. Antes de entrar, acuerdan que una moneda en cara cuenta y una moneda en cruz no cuenta.

El primer prisionero mira todas las monedas que están en cara y calcula el xor de sus índices. Llámalo $S$. Si la casilla secreta tiene número $T$, el primer prisionero debe voltear la moneda de la casilla:

$$ S\oplus T. $$

¿Por qué funciona? Al voltear una moneda, su índice entra o sale del xor total. En ambos casos, el nuevo xor del tablero queda convertido exactamente en $T$.

Después entra el segundo prisionero, calcula el xor de los índices de las monedas que están en cara y obtiene $T$. Ese número le dice cuál era la casilla secreta.