Hace unos años un buen e inquieto amigo (Maese Curro) me escribió un correo acerca de esta historia, la leí y me encantó. Hace unos días jugando con puertas XOR, me acordé de ella y como no, decidí contarla en este lugar de relatos.
Un carcelero le propone el siguiente juego a dos convictos para que puedan salvar su vida. Si aciertan el cuadrado mágico, se salvan, si no, mueren. Explico las normas del malévolo juego.
Participan, un maligno y despiadado carcelero, un convicto que observa y participa en el juego y el convicto adivino.
El carcelero distribuye monedas con caras o cruz aleatoriamente en un tablero de ajedrez, posteriormente elige una moneda como cuadro mágico; en este momento, el convicto participante que ha visto el cuadro mágico, debe cambiar una moneda de cara a cruz o de cruz a cara. Si el penado que acompaña al carcelero que ha visto la distribución, el cuadro mágico y la moneda que él mismo ha cambiado, dijese algo al convicto adivino, mueren ambos. Solo esto.
El reo participante pasa a una habitación aislada y con todo esto y nada, el convicto adivino entra en la sala del tablero de ajedrez y observando este sin saber nada sobre distribuciones, cuadro mágico y moneda cambiada, debe acertar el cuadro mágico elegido por el carcelero. Ohhhhhhhhhh!
Está claro que el convicto adivino, de adivino nada, simplemente debe acordar una estrategia previa con el convicto participante y … hablemos del sistema binario y de paridad.
Lo primero de todo, un tablero tiene 64 casillas y los presos deciden darle un valor de 0 a la primera casilla empezando de izquierda a derecha y de arriba hacia abajo, un 1 a la siguiente y así hasta llegar hasta la última casilla que valdrá 63 tal y como se muestra en la figura de la izquierda, a posteriori convierten sus valores decimales al sistema binario quedando como el tablero de la derecha.
Para los que no recuerden como se convierte de decimal a binario y viceversa, el número 36 por ejemplo equivale en el sistema decimal 3.101+6.100=30+6 y en binario le corresponde el número 100100 1.25+0.24+0.23+1.22+0.21+0.20=1.32+0.16+0.8+1.4+0.2+0.1=36
Para convertir un número de decimal a binario dividimos continuamente por la base guardando los restos de la división, pero al reves; en el ejemplo 36 es dividido entre 2 continuamente y los restos son almacenados como dígitos del número en sistema binario. Recordemos que D = d . C + r, donde el cociente es la base del sistema numérico el divisor es el dividendo de la siguiente división y el resto el dígito. En el post sobre sistemas de numeración posicional en Arithmos, hablo algo más sobre el tema en cuestión.
36=18.2+0, 18=9.2+0, 9=4.2+1, 4=2.2+0, 2=1.2+0, 1=2.0+1, por tanto 36 equivale a 100100
Bueno, ya tenemos un tablero de ajedrez donde podemos determinar mediante un valor binario el cuadro mágico elegido por el carcelero; si este selecciona la casilla 36, el convicto adivino tendrá que adivinar la casilla 100100. ¿Y como? siguiente paso la paridad.
Un tablero de ajedrez tiene 64 casillas, potencia de 2, concretamente 25, de modo que los convictos decidieron dividir el tablero de tantas formas como dígitos tiene el mayor número de este en binario, es decir de 6 formas distintas, para así poder determinar la paridad de caras y cruces en cada una de estas zonas; si existe en cada zona sombreada un número impar de caras, se le asigna un 1 y si es par, un 0 de modo que cuando el carcelero distribuya las monedas, el participante pueda obtener un valor significativo de la paridad del tablero y de este modo cada distribución de paridad, identifica únicamente cada reparto, al cambiar una moneda el valor de paridad es totalmente distinto. Estas eran las zonas de recuento de caras y su peso posicional.
El convicto participante debería encargarse de contar las caras de cada tablero que coincidían con la zona sombreada, si el número de caras era impar, un 1, si era par, un 0, y para entenderlo mejor, lo veremos con un ejemplo sencillo donde los asteriscos simulan la cara de una moneda y donde no hay nada, debería albergar una moneda con cruz.
Este tablero tendría una paridad 011101.
- El primer tablero tiene dos monedas con cara en la zona sombreada, 2 es par, un 0.
- El segundo tiene tres caras sobre la zona sombreada, 3 es impar, un 1
- El tercero tiene tres caras sobre la zona sombreada, 3 es impar, un 1
- El cuarto tiene una cara sobre la zona sombreada, 1 es impar, un 1
- El quinto tiene dos caras sobre la zona sombreada, 2 es par, un 0
- Por último, el sexto, tiene tres caras sobre la zona sombreada, 3 es impar, un 1
No es difícil ¿verdad? pero, en realidad, para el que quiera comprobarlo es una operación XOR de cada posición. Abrimos la calculadora de Windows, menú programador y realizamos la operación XOR sobre las posiciones 0, 9, 18, 25, 27, 32 y 36 que son las casillas del tablero donde existen caras, con resultado 29 que es 011101->29 = 0.32+1.16+1.8+1.4+0.2+1.1.
¿Y que es la operación XOR?, es una operación lógica con la siguiente tabla que equivale a la expresión algebraica (algebra de Boole)
si sus valores son iguales, resultado 0, si son distintos, un 1. Tiene la siguiente propiedad, si al resultado de la operación le volvemos a realizar la operación inversa, obtenemos el valor inicial. Nota 1
(Esto por ejemplo con la suma o con otras operaciones no ocurre, 4+5=9 y 4+9≠5)
fantástico ¿no? 011 XOR 101 = 110 y 110 XOR 101=011, o
Y ya que conocemos como se realiza una operación lógica XOR es cuando estamos dispuestos a resolver el enigma. El carcelero elige el cuadro mágico, por ejemplo la casilla 7 de nuestro sencillo ejemplo que equivale a 000111, de modo que el convicto participante realiza la operación XOR sobre la paridad del tablero y el valor del cuadro mágico 011101 XOR 000111=011010 que equivale al número 26!!!! pues entonces el convicto participante ya sabe que la moneda de la casilla 26 debe darle la vuelta para cambiar la paridad del tablero, quedando la paridad de nuevo en el valor 000111 que es… TACHÁN! EL CUADRO MÁGICO, el número 7 en binario.
De este modo, el convicto adivino solo debe salir, contar las caras en cada zona, calcular la paridad y convertir el número binario a decimal, determinando que la casilla 7 es la elegida por el carcelero.
¿Que ha pasado? Por una parte tenemos la paridad del tablero que es única (operación XOR de los elementos del tablero con cara), llamaremos P1 a la paridad del tablero inicial y cn a las casillas con caras
el carcelero selecciona el cuadro mágico que llamaremos M y el convicto calcula de nuevo XOR para obtener la moneda cambiante C. Al hacer XOR con el cuadro mágico estamos creando un nuevo tablero con una nueva paridad P2 que es igual a la moneda que debe cambiar
El convicto participante cambia la moneda C de cara a cruz o viceversa y ya tenemos un nuevo tablero con una paridad distinta y aquí es cuando la característica de XOR hace su efecto, ¿que dijimos en la nota 1? que si al resultado de una operación XOR se le realiza con uno de los elementos de la operación, obtenemos el otro valor de la operación.
El convicto adivino, sale al escenario y se encuentra un nuevo tablero con una paridad distinta, la calcula y esto es lo mismo que realizar una operación XOR de la primera paridad sobre el valor de la casilla C que cambió y si la primera paridad con el cuadro da como resultado la casilla de cambio, la operación XOR de la paridad inicial con la casilla que cambió debe dar… pues el cuadro mágico.
¿No son preciosas las matemáticas? ¿No es fantástica el algebra de Boole? Pues gracias a esto, puedo escribir este post desde mi ordenador. Los convictos dejaron de serlo y actualmente están trabajando en Google y JetBrains.
Os dejo el enlace a la página que leí hace unos años que además tiene unos tableros interactivos para adivinar y jugar con el cuadro mágico.
Además he creado en C# y WPF un pequeño simulador para windows que podréis encontrar en el siguiente enlace. Descargar el rar y correr el ejecutable (libre de virus y demás, os adjunto el hash) El mio es diferente de la página WEB, pero a mi me gusta más. 😉
El hash SHA-512 del archivo WinRar del enlace es CADC5728F7C59C67B31FB7EA1D7D7F6B694F8390BF308667A937709D3D1D2DBFE5D5C4013800A1CDC36A6486A267C996D01DAA98EE92F007A3138DEB7417B353.
Simulador de DeadXORAlive
Si alguien desea ver el código de la app, en wakicode puede hacerlo.
Pd: El correo de mi buen amigo Curro no tiene desperdicio. Cada vez que veo un correo suyo, lleno el candil de aceite para pasar ratos de lectura, como siempre Paco, gracias por tus letrillas.
«Maese Joaquín, le emborrono estas letrillas, confiando en que a vuesa merced, no le va a hacer falta utilizarlo, pero creo de justicia el proporcionarle el lugar del que extraje el demoníaco acertijo, del tablero de ajedrez y de los dos prisioneros.
Tenga cuidado no estruje el caletre en demasía, que también Alonso Quijano lo fizo con los libros de caballería y mire donde acabó su triste figura.
Recuerde que siempre hay más de una solución, seguro que la suya, es diferente.
http://datagenetics.com/blog/december12014/index.html
De un viejo fisgoneador de papeles y avaro de relatos.»
arithmos 
Un comentario en “Dead XOR Alive”