Una sola moneda puede cambiarse: parece imposible transmitir con eso la ubicación de una entre sesenta y cuatro casillas. Sin embargo, existe una estrategia que lo consigue siempre.
Dos prisioneros, 64 monedas y un escaque secreto
Enunciado
Hay dos prisioneros y un guardia. Sobre un tablero de ajedrez hay una moneda en cada casilla, mostrando cara o cruz. Antes de empezar, los prisioneros pueden acordar una estrategia.
Luego entra el primer prisionero. El guardia le señala una casilla secreta. El primer prisionero puede voltear exactamente una moneda, la que quiera, y después sale.
Entra entonces el segundo prisionero, que ve el tablero resultante pero no sabe qué casilla señaló el guardia.
¿Pueden acordar una estrategia para que el segundo prisionero identifique siempre la casilla secreta?
Ver solución
Solución
Respuesta: sí.
Primero numeran las casillas del 0 al 63. Acuerdan que una moneda en cara cuenta y una 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 voltea la moneda de la casilla:
¿Por qué funciona? Al voltear una moneda, su índice entra o sale del xor total. En ambos casos, el nuevo xor del tablero queda igual a 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.