Se colocan varios montones de piedras y dos jugadores se turnan para quitar piedras. Solo hay dos reglas: en cada turno solo puedes tomar de un montón, y puedes tomar desde 1 piedra hasta el montón entero. Gana quien toma la última piedra. Las reglas son así de simples y, sin embargo, sorprendentemente existe una forma de predecir a la perfección, antes incluso de empezar, quién va a ganar.
El secreto está en operar con la cantidad de piedras de cada montón usando una operación llamada XOR (o exclusivo). El XOR compara dos números dígito por dígito en binario y, en cada posición, da 0 si los dígitos coinciden y 1 si son distintos. Por ejemplo, con montones de [3, 4, 5], en binario son 3=011, 4=100, 5=101. Calculando el XOR dígito por dígito: el primer dígito es 0⊕1⊕1=0, el segundo es 1⊕0⊕0=1 y el tercero es 1⊕0⊕1=0. Así que el valor del XOR es 010, es decir, 2.
Si este valor del XOR (llamado "suma Nim") no es 0, quien tiene el turno en ese momento tiene una jugada que le garantiza la victoria. Basta con calcular el XOR de la cantidad de cada montón con ese mismo valor y buscar el montón en el que el resultado sea menor que la cantidad original. Con [3,4,5], el XOR era 2: 5 XOR 2=7 y 4 XOR 2=6 dan resultados mayores, así que no sirven, pero 3 XOR 2=1 da un resultado menor, así que ese sí sirve. Entonces, si quitas 2 piedras del primer montón (el de 3) y dejas solo 1, los montones quedan en [1,4,5], y ahí el XOR es 1⊕4⊕5=0.
En cambio, si el XOR ya es 0, quien tiene el turno en ese momento está en desventaja. Mientras el rival juegue perfecto, cualquier jugada que hagas dejará el XOR en un valor distinto de 0, y el rival simplemente lo volverá a dejar en 0 cada vez, hasta que al final será él quien tome la última piedra. Por eso la estrategia ganadora del Nim es sorprendentemente simple: "asegúrate siempre de que el XOR sea 0 justo al terminar tu turno".
¿Por qué funciona precisamente con el XOR? El XOR tiene la propiedad de "anular lo que forma pareja". Cuando el juego termina (todos los montones en 0), el XOR también es 0, naturalmente. Y desde un estado en el que el XOR es 0, cambiar un solo montón lo saca de 0 con toda seguridad (porque cambiar un solo montón rompe el equilibrio). Al revés, cuando el XOR no es 0, siempre hay algún montón cuyo desequilibrio lo anula exactamente, lo que te permite volver a dejar el XOR en 0. Estas dos propiedades encajan para que funcione la estrategia ganadora: "si le devuelves siempre el turno a tu rival con XOR=0, al final quedará acorralado".
En nuestra página de actividad, la computadora juega justamente con esta estrategia del XOR, así que si empieza desde una posición ventajosa es realmente difícil vencerla. Pero si usas el botón de pista para revisar el valor del XOR y la jugada recomendada en cada turno, tú también puedes ganarle. Prueba distintas configuraciones de montones y acostúmbrate a revisar desde el principio si el XOR es 0 (es decir, si estás en desventaja) o no.