Cuestión de balance

Juguemos al NIM y aprendamos la estrategia para ganarlo

Por Adrián Paenza May 26, 2019

El juego que voy a presentar ahora es uno de los más antiguos pero no por eso menos sorprendentes que ofrece la Teoría de Juegos, una de las ramas más atractivas de la matemática.

Se llama NIM (*) y las reglas para jugarlo son muy sencillas.

A medida que uno adquiere experiencia, comienza a planificar estrategias para ganar. Al principio es desconcertante, pero luego resulta elegante y seductor.

Las reglas

Uno empieza con un cierto número de monedas (o fósforos, o palillos o ‘porotos’) que aparecen distribuidas en diferentes filas. No hay restricciones: usted dispone con cuántas filas se va a jugar y también hay libertad para decidir cuántas monedas por fila.

Participan del juego dos competidores. Cada uno de ellos puede ‘retirar’ de cada fila la cantidad de monedas que elija, incluso todas de una vez. Eso sí: sólo de una sola fila.

Luego le toca al siguiente jugador, que tiene que hacer lo mismo: retirar un número cualquiera de monedas, pero siempre deben ser seleccionadas de una sola de las filas.

Se van alternando uno y otro participante, hasta que no queden más monedas.

¿Quién gana? Gana el que retira la última moneda. Es decir, gana de los dos competidores, el último que se queda con la última (o últimas) moneda (s).

Estrategia ganadora

Antes que nada, al juego hay que jugarlo. Es decir: juéguelo. No una vez, sino muchas. Enfréntese con diferentes situaciones. Analice qué hacer. Seguro que se va a tropezar pensando por usted pero también analizará qué podría hacer su rival. Disfrute de hacerlo. Cada situación es distinta y cada movimiento del otro jugador podrá sorprenderlo con algo que no pensó.

Es más: me atrevo a decir que usted debería parar de leer acá, y retomar recién cuando haya jugado mucho, o al menos cuando ya le tenga tomado el pulso al NIM. ¿Qué gracia tiene, si no, leer cómo hacer para ‘ganar siempre’?

Una vez que practicó muchas veces (y encontró múltiples dificultades, ganó y perdió) entonces sí, cabe preguntarse: ¿habrá alguna estrategia ganadora?

Es decir, ¿será posible encontrar alguna forma de jugar para alguno de los dos participantes de manera que quien la aplique gane siempre, sin importar lo que haga el otro?

Por último, el hecho de que haya una estrategia ganadora no significa que sea fácil encontrarla, ni mucho menos.

Más aún: en este caso sí, la hay, pero creo que es muy difícil de encontrar (ver (**)).

Por eso lo atractivo es jugar al juego y planificar uno qué hacer, aunque no sepa o no conozca la estrategia general para ganar siempre. Por eso, lo/la invito a que disfrute del trayecto.

¿...Jugó ya? Ahora sí, entonces. Lo que sigue requiere del uso de la matemática en su más pura expresión. En principio, porque hay que pensar todo el tiempo. ¿Qué pasa? Dije pensar. ¿No le resulta muy atractivo que alguien le proponga pensar para resolver un problema?

¿Se acuerda de las potencias de 2? Es decir, de los números: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1.024, etc.

Estos números provienen de multiplicar varias veces el número 2 (con la excepción del ‘1’, que proviene de hacer 2⁰). O sea,

1 = 2⁰

2 = 2¹

4 = 2²

8 = 2³

16 = 2⁴

32 = 2^{5 (**)}

64 = 2⁶

128 = 2⁷

256 = 2⁸

512 = 2⁹

1.024 = 2¹⁰ ...y así siguiendo

Ahora le propongo repensar algo. Tome un número cualquiera, digamos 27 por poner un ejemplo (pero usted elija uno por su cuenta). Trate de escribir el número que eligió (yo lo voy a hacer con el 27) como suma de los números que figuran en la lista (**).

El número 27 se escribe así:

27 = 16 + 8 + 2 + 1

Si hubiera elegido el 151, entonces

151 = 128 + 16 + 4 + 2 + 1.

Es decir, cualquier número natural que uno elija, se puede escribir de una única forma, como suma de potencias de 2.

Ahora volvemos al juego. Tome la primera fila y fíjese cuántas monedas hay. Agrúpelas (sin sacarlas del lugar) en potencias de 2. Y luego, repita el procedimiento con las siguientes filas.

Veamos rápido algunos ejemplos.

Ejemplo 1: supongamos que uno tiene esta distribución de monedas por fila:

Ahora ‘escribimos’ cada uno de estos números como suma de potencias de 2, y resulta lo siguiente

25 16 8 1

15 8 4 2 1

9 8 1

7 4 2 1

5 4

3 2 1

2 2

1 1

Lo que hice fue agrupar en cada fila todas las monedas que había, pero las separé de acuerdo con las potencias de 2. Un dato complementario (pero muy importante): esta manera de agruparlas es única . Es decir, cada número puede escribirse de una única manera como suma de potencias de dos (y esto da lugar a lo que se llama la escritura binaria, que es la que usan las computadoras).

Ejemplo 2:

51 32 16 2 1

46 32 8 4 2

27 16 8 1

19 16 2 1

15 8 4 2 1

7 4 2 1

1 1

Ejemplo 3:

26 16 8

16 16

14 8 4 2

7 4 2 1

1 1

Bien. Creo que con estos tres ejemplos se entiende lo que uno hace con las monedas de cada fila.

Ahora voy a explorar cada uno de ellos. Voy a contar cuántos números aparecen ahora en cada columna (una vez agrupados en potencias de 2).

En el ejemplo 1, en la primera columna hay un número ‘16’, en la segunda columna aparecen tres números ‘8’. En la tercera (columna) hay tres números ‘4’. En la cuarta, cuatro números ‘2’, y por último, en la columna final, hay siete números ‘1’.

O sea, si escribo lo que acabo de encontrar (y agrego una fila al final), se tiene:

25 16 8 1

15 8 4 2 1

9 8 1

7 4 2 1

5 4 1

3 2 1

2 2

1 1

1 3 3 4 7 (***)

Ahora, para confirmar las ideas que expuse recién, hago lo mismo con los dos ejemplos que faltan: 2 y 3.

Ejemplo 2:

51 32 16 2 1

46 32 8 4 2

27 16 8 1

19 16 2 1

15 8 4 2 1

7 4 2 1

1 1

2 3 3 3 5 6 (***)

Ejemplo 3:

26 16 8

16 16

14 8 4 2

7 4 2 1

1 1

2 2 2 2 2 (***)

Ahora voy a usar un par de nombres. Se dice que una posición del juego cualquiera está balanceada, si todos los números que figuran en la última fila (la última que agregué en (***)) son pares. Y si no, se llama desbalanceada. Como se ve, el ejemplo 1 provee una posición desbalanceada (ya que aparecen varios números impares en la última fila).

El ejemplo 2, provee también una posición desbalanceada:

51 32 16 2 1

46 32 8 4 2

27 16 8 1

19 16 2 1

15 8 4 2 1

7 4 2 1

1 1

2 3 3 3 5 6 (***)

En cambio, en el ejemplo 3:

26 16 8

16 16

14 8 4 2

7 4 2 1

1 1

2 2 2 2 2 (***)

En este caso sí, las columnas están todas balanceadas, porque la última fila consiste de todos números pares.

Ahora viene la parte interesante (y lo invito a que reflexione sobre lo que va a leer): si una posición está desbalanceada, entonces siempre se puede ‘balancear’ reduciendo las monedas de una sola fila. Esto es muy importante, porque dice que si se tropieza con una posición ‘desbalanceada’, cualquier jugador la puede ‘balancear’ con un movimiento lícito.

Inicialmente lo voy a hacer con un ejemplo de manera tal de poder aclarar las ideas. Espero que usted esté de acuerdo conmigo.

Supongamos que uno tiene esta distribución de monedas:

121, 83, 57, 46, 29, 17, 12, 6 y 3.

Las agrupo de acuerdo con las potencias de 2 y me fijo al final está balanceada o no.

121 64 32 16 8 1

83 64 16 2 1

57 32 16 8 1

46 32 8 4 2

29 16 8 4 1

17 16 1

12 8 4

6 4 2

3 2 1

2 3 5 5 4 4 6 (***)

Uno descubre que está desbalanceada (¿entiende por qué?). Es que en la última fila, la fila (***), aparecen varios números impares.

Para balancearla, lo que uno hace es fijarse en la fila (***) cuál es la potencia de 2 más grande que aparece con un número impar. O sea, qué número de la fila (***) es impar y es el que está ‘más’ a la izquierda de todo el resto. En el ejemplo, resulta ser ‘32’, ya que figura tres veces.

Uno elige una fila cualquiera que contenga al número ‘32’, digamos la tercera fila (que sirvió para desarrollar el número ‘46’).

Ahora voy a hacer de cuenta como si esta fila, la del ‘46’ no existiera: la ignoro.

Es como si empezara todo de nuevo, incluso escribiendo la nueva fila (***), pero ignorando el número ‘46’.

La última fila, la fila (***), puede que cambie en la paridad de algunos números. O sea, algunos de los que estaban pares podrán pasar a ser impares, o al revés, o quedar como está, pero lo que es seguro es que todos los potenciales cambios tienen que producirse a la derecha del ‘32’, porque las potencias de 2 que figuran a la izquierda de 32 no las toco (eso sucede porque elegí ‘32’, como la más grande de todas las que aparecen un número impar de veces)

Por eso, al excluir la fila del 46, entonces se ve que quedan siendo impares:

el 16 (aparece 5 veces),
NO el ‘8, porque al excluir el 46 nos ‘llevamos’ un 8, por lo que ahora quedan sólo cuatro números ‘8’,
Queda impar la del ‘4’ (aparecen tres números ‘4’ al obviar el 46)
Queda impar la del ‘2’, por la misma razón
Y por último, queda un número par (seis en total) números ‘1’.

¿Cómo hacer para balancear lo que está desbalanceado? (Piénselo un rato en soledad).

Lo que hay que hacer es sumar:

16 + 4 + 2 (porque son las tres potencias de 2 que quedaron impares)

Y esta suma resulta ser 22.

Entonces reemplazamos la pila del 46, por 22 (o sea, si uno está jugando el juego, tiene que restar 16) y de esa forma ahora reemplazamos la fila del 46 por una de 22, y se tiene:

121 64 32 16 8 1

83 64 16 2 1

57 32 16 8 1

22 16 4 2

29 16 8 4 1

17 16 1

12 8 4

6 4 2

3 2 1

2 2 6 4 4 4 6

Habiendo hecho esto, hemos logrado balancear la posición.

En resumen, lo que hay que hacer es lo siguiente (para balancear una posicion desbalanceada):

Fíjese cuál es la mayor potencia de 2 que está desbalanceada. Elija esa fila (si hay varias, elegir una cualquiera).
Ignore esa fila (o ese número si se prefiere), y fíjese cómo queda la posición ahora. Es decir, como si ese número no hubiera existido. Uno mira cuáles son las potencias de dos que quedan desbalanceadas habiendo excluido esa fila.
Lo que uno hace es reemplazar la fila que estaba ignorando por la suma de las potencias de dos que quedaron desbalanceadas. Con eso, uno se asegura que ahora todas las potencias de dos quedan balanceadas y por lo tanto, la posición final es balanceada.

Esto acaba de demostrar que toda posición desbalanceada se puede balancear, sólo modificando una fila, lo que significa que uno lo puede lograr haciendo un movimiento lícito..

En el ejemplo 2:

51 32 16 2 1

46 32 8 4 2

27 16 8 1

19 16 2 1

15 8 4 2 1

7 4 2 1

1 1

2 3 3 3 5 6 (***)

Me fijo en la mayor potencia de 2 de la fila (***) que es impar. En este caso, resulta ser la columna del ‘16’, ya que hay tres números 16. Elijo una fila cualquiera que contenga al 16. Por ejemplo, la fila del ‘19’. Ahora, me fijo en lo que queda, excluyendo la fila del 19.

Ejemplo 2:

51 32 16 2 1

46 32 8 4 2

27 16 8 1

19 16 2 1

15 8 4 2 1

7 4 2 1

1 1

2 2 3 3 4 5 (***)

Ahora, las potencias de 2 que resultan impares son, la del ‘8’, la del ‘4’ y la del ‘1’.

Los sumo y quedan:

8 + 4 + 1 = 15

Lo que tengo que hacer es reemplazar en la fila del 19 (que estaba ignorando hasta acá) y poner 15. Es decir, en la práctica, si estuviera jugando al NIM con alguna otra persona, lo que tengo que hacer es retirar cuatro monedas de la fila del 19. En ese caso, se tiene la siguiente situación:

51 32 16 2 1

46 32 8 4 2

27 16 8 1

15 8 4 2 1

7 4 2 1

1 1

2 2 4 4 4 6 (***)

Luego, la fila (***) quedó con todos números pares y por lo tanto, hemos balanceado la posición. Esto significa que uno, haciendo movimientos lícitos balancea cualquier posición desbalanceada.

Ahora, al revés. ¿Qué sucede si una posición ya está balanceada? Entonces lo que quiero hacer ahora es convencerla/o que cualquier cosa que haga, la va a desbalancear.

Esto hay que interpretarlo así: si la posición es balanceada, esto significa que todas las potencias de dos que aparecen en todas las filas son necesarias, para que al final, en la fila (***) queden todos números pares. Al quitar cualquier moneda, uno desbalancea la posición.

Justamente, si uno empieza con una fila cualquiera, al tocar cualquier moneda, hace desaparecer una (o más) potencias de dos, que eran necesarias para mantener la posición balanceada. Podrían incluso aparecer otras potencias de dos, pero también desbalancearían la posición porque todo lo que hay en el resto no se modifica.

Es decir, al alterar cualquier fila inexorablemente desbalancea la posición.

Ahora sí, la estrategia ganadora.

Lo importante de lo que aprendimos recién es que si uno encuentra una posición desbalanceada, la puede balancear con movimientos legales. A su vez, si a uno le toca jugar con una posición que ya está balanceada, no puede impedir desbalancearla.

Teniendo esto en cuenta, cuando el juego se termine, o sea, cuando uno de los competidores se queda con la última moneda (o las últimas, si es que quedaron más en una sola fila), esa posición (cuando ya no quedan monedas) está balanceada. Luego, el último jugador, encontró en el último tramo, una posición desbalanceada… y la balanceó (para terminar ganando).

Es decir que, jugando como expliqué más arriba, un jugador balancea, y al siguiente no le queda más remedio que desbalancear. Lamentablemente para el jugador que desbalancea cada vez que juega, va a perder (por supuesto, si los dos saben jugar al NIM). Es decir, que si uno quiere ganar siempre, tienen que pasar las siguientes cosas:

Si la posición inicial está desbalanceada, el que empieza, gana
Si la posición inicial está balanceada, el que empieza, pierde.

Por supuesto, todo esto requiere de que ambos jugadores sepan usar la estrategia explicada más arriba. Si no, si uno juega libremente y sin estar sujeto a ninguna elaboración pierde uno puede o bien ganar o bien perder independientemente de que las posiciones estén balanceadas o no.

Moraleja

Uno puede jugar al NIM y hacerlo muy bien sin necesidad de saber nada de lo que está expuesto más arriba.

Sin embargo, la idea de cómo hacer para ganar siempre es algo que se conoce hace muchos años y aparece profusamente en la literatura que habla del NIM.

Como usted habrá detectado ya, es una estrategia no trivial y es muy poco probable que a uno se le ocurra sólo/a.

Por eso lo invito a que no se desespere si al leer este segmento pensó que ni siquiera los juegos son para usted. No. Los juegos son para todos, para entrenar la mente y para pensar. ¿Y quien dijo que si usted no le dedicara muchas horas a pensar en el NIM no se le hubiera ocurrido cómo hacer para ganar?

(*) El NIM aparece en la literatura como inventado por C. L. Bouton de la Universidad de Harvard alrededor del año 1901. Se supone que el nombre (NIM) tuvo su origen en la palabra alemana nehmen (‘tomar’ o ‘retirar’), cuya forma imperativa en singular es nim.

--------------------------------

Para suscribirte con $ 1000/mes al Cohete hace click aquí

Para suscribirte con $ 2500/mes al Cohete hace click aquí

Para suscribirte con $ 5000/mes al Cohete hace click aquí