El juego del NIM

Se sabe que la palabra “nim”, hoy día en desuso, proviene del inglés antiguo y que entonces  significaba la acción de robar o coger algún objeto. Hay un juego muy popularizado que lleva este nombre y cuyo desarrollo hace honor a dicha palabra. Antes de continuar en este texto convendría al lector jugar la versión general disponible en la siguiente dirección electrónica: http://www.juegosagogo.com/mesa/juego/5596-nim-master

Como habrá notado resulta difícil conseguir la victoria por encima del programa, sobre todo cuando la versión no permite al jugador elegir entre ser el primero en jugar o el segundo. Pero para entrañar la solución de este juego de estrategia conviene analizar una versión más simplificada del juego del NIM.

Juego del NIM simplificado.

Hay dos jugadores y un montón con 19 piedras sobre la mesa. Cada jugador puede recoger 1,2 o 3 piedras por turno mientras queden suficientes. Para llegar a la victoria se debe ser el último en lograr recoger piedras. El que no pueda hacerlo es el perdedor. ¿Cómo proceder para garantizar la victoria?

Para iniciar el análisis procedamos inductivamente, es decir, estudiando cada juego para 1, 2, 3, 4,… y n piedras. De aquí en adelante el primer jugador en tirar será representado por la letra A, y B el segundo.

Número de piedras (n)	Jugador A	Jugador B	Perfil de estrategias por turnos (t1,t2,t3,…)
n=1	Gana		(1,0)
n=2	Gana		(2,0)
n=3	Gana		(3,0)
n=4		Gana	Tres casos (1,3):(2,2):(3,1)
n=5	Gana		Tres casos (1,1,3):(1,2,2):(1,3,1)
n=6	Gana		Tres casos (2,1,3):(2,2,2):(2,3,1)
n=7	Gana		Tres casos (3,1,3):(3,2,2):(3,3,1)
n=8		Gana	Tres casos (1,3,copia n=4):(2,2,copia n=4):(3,1,copia n=4)

Basta con estudiar estos casos para descubrir el desarrollo completo del juego para cualquier n. El juego regresa a la misma situación en un periodo de longitud 4. Las posiciones donde el primer jugador gana corresponden a valores de n en el conjunto {1,2,3,5,6,7,9,10,11,13…}, las cuales designaremos como V(A). Por otro lado las posiciones donde el segundo jugador puede llegar a la victoria son V(B) = {4,8,12,16,…}  Y digo “puede" porque cabría la posibilidad de errar en el juego si no se conoce bien el algoritmo de la estrategia ganadora.

El secreto se halla en el caso n=4. El jugador B gana ya que A comerá a lo mucho 3 piedras y a lo menos 1, dejando el rango de posibilidades de B dentro de las jugas permisibles. En el caso n = 5, el jugador A aprendió la lección y se come 1 para que al sobrar 4 él tome el papel de segundo jugador. Lo mismo sucede con n=6 y n=7, A coge lo que lo separa del caso n=4. Por lo tanto la estrategia de A, E(A), consiste en “comerse el residuo modulo 4 de n”, cuando n=5=4(1)+1, se come 1; cuando n=6=4(1)+2, se come 2 y con n= 7=4(1)+3 se come 3. Y esto se repetirá siempre: gano cada vez que me como el sobrante para llegar al múltiplo inferior de 4 más inmediato.

Pero cuando n=8, el jugador A ya no puede repetir su estrategia, pues para llegar a 4 debería comerse 4, lo cual es imposible en las reglas del juego. Entonces E(B) consiste en conservar la posición privilegiada de dejar al otro jugador en la imposibilidad de llegar al múltiplo inferior de 4 más cercano. Para ello utiliza la estrategia de completar modulo 4. Si A tira 1, B tira con 3, (2,3) y (3,1), como se observa en la tabla.

Para el caso que analizábamos, n = 19 =4(4)+3, es una posición V(A). Si se permitiera escoger el turno conviene ser el primero.

Si ahora pensamos el caso general, que es el impulso predilecto de un matemático, formularíamos el siguiente resultado:

Proposición 1 (NIM simplificado):

 Sea n,kÎN. En un juego de NIM donde hay n piedras y la estrategia de cada jugador consiste en tomar 1, ó 2,…, ó k objetos, entonces:

V(A)= {mÎN tales que m º 1,2,3,…,k mod (k+1)    y

V(B)= {mÎN tales que m º 0 mod(k+1); además

Si n= (k+1)p + r, y r no es cero, entonces E(A) consiste en comer r piedras y si B tira con j piedras, A contesta con k+1-j.  O sea la partida sería de la forma: (r,j¹,k+1-j¹,j²,k+1-j²,…,k+1-j^p)

Si r=0, E(B) consiste en contestar la tirada de A en  j piedras con k+1-j. La partida sería: (j¹,k+1-j¹,j²,k+1-j²,…,k+1-j^p),

donde el tamaño de la partida es 2p+1 o 2p.

Que en buen lenguaje cristiano significa que si hay 666 piedras y se pueden tomar entre 1 y 7, entonces basta con dividir el número 666 entre (7 + 1) y ver cuánto sobra. Si no sobra nada entonces gana el jugador B; si sobra algo gana el jugador A. En este caso 666/8 = 83(8) + 2, sobran 2: gana A.

Siempre es posible decidir si en un juego de NIM simplificado conviene tirar primero o segundo para garantizar la victoria, sin embargo, de acuerdo a la proposición 1 hay otra variante que podemos jugar.

NIM  k-variante simplificado.

Formulémoslo así: hay n piedras y los jugadores van a disputar un Juego de juegos. Cada juego, digamos J_k es un nim simplificado donde se pueden coger 1,2,…,k piedras en cada tirada, donde k está entre 1 y n-1. Gana el jugador que haya ganado más J_k juegos NIM.

Por ejemplo, pensemos en n = 6 piedras, habrá 5 juegos a disputar: J¹,J²,…,J⁵. Apliquemos la proposición 1 a cada caso para hacer un balance en el Juego de juegos.

Juego	Criterio de proposición 1, n=6.	Ganador
J1	6 º 0 mod (2)	Gana B
J2	6 º 0 mod (3)	Gana B
J3	6 º 2 mod (4)	Gana A
J4	6 º 1 mod (5)	Gana A
J5	6 º 0 mod (6)	Gana B

En este caso la victoria en el Juego de juegos recae en B. Parece entonces que para cada n hay que analizar las siguientes congruencias:

Juego	Criterio de proposición 1	Ganador
J1	n º i1 mod (2)	Gana ?
J2	n º i2 mod (3)	Gana ?
J3	n º i3 mod (4)	Gana ?
J4	n º i4 mod (5)	Gana ?
J5	n º i5 mod (6)	Gana ?
…	…	…
Jn-1	n º in-1 mod (n)	Gana B

Cuando i_k es 0 gana el jugador B. En los demás casos gana A. A todas vistas los juegos que benefician al segundo jugador son los valores donde k+1 resulta ser divisor de n. En el ejemplo n igual a 6 tenemos lo siguiente: n = 2¹x3¹, cuyo número de divisores, según la Teoría de Números es (1+1)(1+1)= 4, al cual le restamos 1, que es el caso cuando k=0, claramente fuera de las reglas del juego. Este primer paso da una gran desventaja para el jugador B en números grandes, pues la experiencia nos dice que en general un número tiene menos divisores enteros que no enteros y el caso n = 6 es especial.

Para decir que B tiene desventaja sobre A en el NIM k-variante simplificado estaríamos asegurando que el número de divisores de n es inferior a su mitad para casos cuando éste es mayor a seis. Es decir:

Proposición 2.

Sea nÎN, con n>6. En un juego NIM k-variante simplificado, A domina el juego.

La prueba es sencilla, para ello sólo se demuestra que D(n) < n/2. Ningún divisor de n mayor que 6, supera a su mitad (no contar a n mismo), pues de existir, al duplicarlo, que es la mínima multiplicidad, rebasaría a n. Entonces en el mejor de los casos todos los números inferiores o iguales a la mitad tendrían que dividir a n, lo cual solo se cumple para n=4 y 6.

Por último se intuye que hay Juegos de juegos donde B nunca gana más que en el juego trivial donde se toman n-1 objetos. Tan sólo considere el caso cuando n es primo, donde A es absolutamente dominante.

Cerremos así este apartado y pasemos al caso del NIM general.

NIM Clásico.

El caso general expuesto en la dirección electrónica se formula así: Sobre la mesa hay n montones, cada uno con x_i piedras. Cada jugador solo puede coger piedras de un montón, desde una hasta todo el montón incluso. Gana el jugador que retire la última piedra.

Se nota claramente la dificultad pero podemos empezar así:

Ejemplo: hay 2 montones, uno de ellos con 7 piedras y el otro con 9. Para ganar cada jugador debe garantizar su jugada una vez que el contrincante haya tirado. Y esto me recuerda otro juego que es de utilidad. Hay una mesa rectangular y dos jugadores. Cada jugador puede poner sobre la mesa cualquier cantidad de fichas. Gana el que logra colocar la última ficha. ¿Cómo ganar? La respuesta es simple pero ingeniosa:

El primer jugador pone una ficha en el centro de la mesa. Al tirar su enemigo éste copiará la posición por simetría, es decir, coloca una ficha a igual distancia sobre la línea que une la ficha central con la que puso el oponente. Esto le garantiza asegurar siempre su próxima tirada.

En el ejemplo claramente gana A. Basta “dejar en pares” el juego de B, digamos que toma 2 del montón grande y deja el juego en (7,7). Si B contesta comiéndose 3 piedras de cualquier montón, A come 3 en el otro: (4,4). Lo que sea que haga B, A copia su tirada en el otro montón, de igual manera que en el juego de la mesa y las fichas el primer jugador usa las líneas de simetría.

¿Qué sucede entonces cuando hay tres o más montones? La clave está en la noción de “dejar en pares”. El sistema binario ofrece gran apoyo, ya que en él hay unidades, montones de 2¹, 2²,2³, …2ⁿ objetos. Si en un juego de NIM clásico hay una configuración del tipo: (x₁,x₂,x₃, …, x_n), basta transformar a sistema binario el número de piedras de cada montón. Si en él hay un número par de montones de cada tipo, es decir montones individuales, de dos, cuatro, ocho, etc., piedras, entonces conviene que el otro jugador empiece tirando para que nosotros apliquemos la técnica espejo de copiar su tirada. O en su defecto, conviene llevar la configuración del juego a un estado “perfectamente apareado” para dejar que el otro jugador inicie en esa configuración.

El punto crucial consiste en garantizar que esto pueda llevarse a cabo, a saber, que siempre es posible llegar a  estados “perfectamente apareados” (PA), y que el siguiente jugador no puede tirar en un estado PA y dejar el juego en otro PA.

Para probar esto formalicemos qué es un estado PA. Para ello se define la suma NIM de la siguiente manera:

Sea (x₁,x₂,x₃, …, x_n) una configuración de NIM clásico, y para cada i, sea  x_i=(bⁱ_m bⁱ_m-1… bⁱ₁ bⁱ₀) su expresión binaria, entonces x_i Å x_j = (bⁱ_m bⁱ_m-1… bⁱ₁ bⁱ₀) Å (b^j_m jⁱ_m-1… b^j₁ b^j₀)= =(z_m z_m-1…z₁ z₀), con z_k = bⁱ_k + b^j_k (mod 2), es decir, z_k = 1 si bⁱ_k + b^j_k = 1, y z_k = 0 en el otro caso.

En forma simple hay un estado PA, cuando al realizar la suma en binario del número de piedras en cada montón por columnas (sin llevar) se obtienen puros ceros, esto es hay un número par de montones de cada tipo.

Es fácil ver que si estamos en un estado PA y se realiza una tirada, es decir, se retira cierto número de piedras de un montón, entonces no podemos obtener otro PA, ya que coger piedras significa que en algún montón, la expresión binaria pierde unos y los sustituye por ceros o viceversa. Esto cambia el número de unos que aparecen en alguna columna y por lo tanto si algún z_k era 0, se volverá 1. Por otro lado pasar de un estado no PA, a uno PA consiste en  conseguir que en las columnas impares agreguemos unos, quitándolos de los montones más grandes.

Todas estas ideas se resumen en un teorema famoso que asegura cómo ganar el NIM clásico.

Teorema de Bouton:

Sea  (x₁,x₂,x₃, …, x_n) una configuración de NIM clásico. Si la suma NIM del número de piedras en cada montón en base 2 consta de puros ceros, entonces el jugador B tiene estrategia ganadora. 

Resolvamos el caso que se muestra en la siguiente figura:

Tenemos:

No. Piedras	Binario
3 piedras	11
5 piedras	101
9 piedras	1001
6 piedras	110
9 piedras	1001

Cuya suma NIM es (0,0,0,0), que es un estado PA, por lo cual ganará el jugador B. Compruébelo y sepa cuándo ganará en el NIM master.