Nim

Nim es un juego matemático de estrategia en el que dos jugadores se turnan para quitar (o "nimming") objetos de distintos montones o montones. En cada turno, un jugador debe eliminar al menos un objeto y puede eliminar cualquier cantidad de objetos, siempre que todos provengan del mismo montón o pila. Dependiendo de la versión que se esté jugando, el objetivo del juego es evitar tomar el último objeto o tomar el último objeto.

Las variantes de Nim se han jugado desde la antigüedad. Se dice que el juego se originó en China, se parece mucho al juego chino de 捡石子 jiǎn-shízi, o "recoger piedras", pero el origen es incierto; las primeras referencias europeas a Nim son de principios del siglo XVI. Su nombre actual fue acuñado por Charles L. Bouton de la Universidad de Harvard, quien también desarrolló la teoría completa del juego en 1901, pero los orígenes del nombre nunca se explicaron por completo.

Nim normalmente se juega como un juego misère, en el que el jugador que toma el último objeto pierde. Nim también se puede jugar como un juego de juego normal en el que gana el jugador que toma el último objeto. Esto se llama juego normal porque el último movimiento es un movimiento ganador en la mayoría de los juegos, aunque no es la forma normal en que se juega Nim. Ya sea en el juego normal o en un juego misère, cuando el número de montones con al menos dos objetos es exactamente igual a uno, el jugador que toma el siguiente puede ganar fácilmente. Si esto elimina todos o todos menos uno de los objetos del montón que tiene dos o más, entonces ningún montón tendrá más de un objeto, por lo que los jugadores se ven obligados a alternar la eliminación de exactamente un objeto hasta que finalice el juego. Si el jugador deja un número par de montones distintos de cero (como lo haría en el juego normal), el jugador toma el último; si el jugador deja un número impar de montones (como haría el jugador en el juego misère), entonces el otro jugador toma el último.

El juego normal Nim (o más precisamente el sistema de nimbers) es fundamental para el teorema de Sprague-Grundy, que básicamente dice que en el juego normal cada juego imparcial es equivalente a un montón de Nim que produce el mismo resultado cuando se juega en paralelo con otros juegos imparciales de juego normal (ver suma disyuntiva).

Si bien a todos los juegos normales de juego imparcial se les puede asignar un valor Nim, ese no es el caso bajo la convención misère. Solo se pueden jugar juegos domesticados usando la misma estrategia que misère Nim.

Nim es un caso especial de un juego poset donde el poset consiste en cadenas inconexas (los montones).

La gráfica de evolución del juego de Nim con tres montones es igual a las tres ramas de la gráfica de evolución del autómata Ulam-Warburton.

En la Feria Mundial de Nueva York de 1940, Westinghouse exhibió una máquina, el Nimatron, que hacía de Nim. Desde el 11 de mayo de 1940 hasta el 27 de octubre de 1940, solo unas pocas personas pudieron vencer a la máquina en ese período de seis semanas; si lo hacían, se les presentaba una moneda que decía Nim Champ. También fue uno de los primeros juegos electrónicos computarizados. Ferranti construyó una computadora para jugar a Nim que se exhibió en el Festival de Gran Bretaña en 1951. En 1952, Herbert Koppel, Eugene Grant y Howard Bailer, ingenieros de W. L. Maxon Corporation, desarrollaron una máquina que pesaba 23 kilogramos (50 lb) que jugaba a Nim contra un oponente humano y ganó regularmente. Se ha descrito una máquina de juego Nim hecha de TinkerToy.

El juego de Nim fue el tema de la columna Juegos matemáticos de febrero de 1958 de Martin Gardner en Scientific American. Se reproduce una versión de Nim, y tiene una importancia simbólica, en la película francesa New Wave Last Year at Marienbad (1961).

Juego e ilustración

El juego normal es entre dos jugadores y se juega con tres montones de cualquier cantidad de objetos. Los dos jugadores se alternan tomando cualquier número de objetos de cualquiera de los montones. El objetivo es ser el último en tomar un objeto. En el juego misère, el objetivo es, en cambio, garantizar que el oponente se vea obligado a tomar el último objeto restante.

El siguiente ejemplo de un juego normal se juega entre los jugadores ficticios Bob y Alice, que comienzan con montones de tres, cuatro y cinco objetos.

Posiciones ganadoras

La estrategia práctica para ganar en el juego de Nim es que un jugador coloque al otro en una de las siguientes posiciones, y en cada turno sucesivo debería poder hacer una de las más pequeñas posiciones. Solo el último movimiento cambia entre misere y el juego normal.

* Solo válido para el juego normal.

** Solo válido para misere.

Para las generalizaciones, n y m pueden tener cualquier valor > 0, y pueden ser iguales.

Teoría matemática

Nim se ha resuelto matemáticamente para cualquier cantidad de montones y objetos iniciales, y hay una forma fácil de calcular para determinar qué jugador ganará y qué movimientos ganadores están disponibles para ese jugador.

La clave de la teoría del juego es la suma digital binaria de los tamaños de heap, es decir, la suma (en binario), ignorando todos los acarreos de un dígito a otro. Esta operación también se conoce como "bitwise xor" o "suma de vectores sobre GF(2)" (suma bit a bit módulo 2). Dentro de la teoría de juegos combinatorios se suele denominar nim-sum, como se denominará aquí. La suma mínima de x y y se escribe x ⊕ y para distinguirlo de la suma ordinaria, x + y. Un ejemplo del cálculo con montones de tamaño 3, 4 y 5 es el siguiente:

Binary Decimal

0112 310 Heap A
1002 410 Salto B
1012 510 Heap C
-...
0102 210 El nim-sum de los montones A, B y C, 3 ⊕ 4 ⊕ 5 = 2

Un procedimiento equivalente, que a menudo es más fácil de realizar mentalmente, es expresar los tamaños de montón como sumas de distintas potencias de 2, cancelar pares de potencias iguales y luego sumar lo que queda:

3 = 0 + 2 + 1 = 2 1 Heap A
4 = 4 + 0 + 0 = 4 Heap B
5 = 4 + 0 + 1 = 4 1 Heap C
----------------------------------------------------
2 = 2 Lo que queda después de cancelar 1s y 4s

En el juego normal, la estrategia ganadora es terminar cada movimiento con una suma mínima de 0. Esto siempre es posible si la suma mínima no es cero antes del movimiento. Si la suma mínima es cero, el siguiente jugador perderá si el otro jugador no comete un error. Para averiguar qué movimiento realizar, sea X la suma mínima de todos los tamaños de almacenamiento dinámico. Encuentre un montón donde la suma mínima de X y el tamaño del montón sea menor que el tamaño del montón; la estrategia ganadora es jugar en tal montón, reduciendo ese montón a la suma mínima de su tamaño original con X. En el ejemplo anterior, tomar la suma mínima de los tamaños es X = 3 ⊕ 4 ⊕ 5 = 2. Las sumas nim de los tamaños de montón A=3, B=4 y C=5 con X=2 son

A ⊕ X = 3 ⊕ 2 = 1 [Desde (011) ⊕ (010) = 001 ]

B ⊕ X = 4 ⊕ 2 = 6

C ⊕ X = 5 ⊕ 2 = 7

El único montón que se reduce es el montón A, por lo que el movimiento ganador es reducir el tamaño del montón A a 1 (eliminando dos objetos).

Como caso simple particular, si solo quedan dos montones, la estrategia es reducir la cantidad de objetos en el montón más grande para que los montones sean iguales. Después de eso, no importa qué movimiento haga tu oponente, puedes hacer el mismo movimiento en el otro montón, garantizando que tomas el último objeto.

Cuando se juega como un juego misère, la estrategia de Nim es diferente solo cuando el movimiento de juego normal dejaría solo montones de tamaño uno. En ese caso, el movimiento correcto es dejar un número impar de montones de tamaño uno (en el juego normal, el movimiento correcto sería dejar un número par de dichos montones).

Estas estrategias para un juego normal y un juego misère son las mismas hasta que el número de montones con al menos dos objetos sea exactamente igual a uno. En ese momento, el siguiente jugador elimina todos los objetos (o todos menos uno) del montón que tiene dos o más, por lo que ningún montón tendrá más de un objeto (en otras palabras, todos los montones restantes tendrán exactamente un objeto cada uno), por lo que los jugadores se ven obligados a alternar la eliminación de exactamente un objeto hasta que finaliza el juego. En el juego normal, el jugador deja un número par de montones distintos de cero, por lo que el mismo jugador toma el último; en el juego misère, el jugador deja un número impar de montones distintos de cero, por lo que el otro jugador toma el último.

En un juego de misère con montones de tamaños tres, cuatro y cinco, la estrategia se aplicaría así:

A B C nim-sum

3 4 5 0102=210 Tomo 2 de A, dejando una suma de 000, así que ganaré.
1 4 5 0002=010 Tomas 2 de C
1 4 3 1102= 610 Cojo 2 de B
1 2 3 0002=010 Tomas 1 de C
1 2 2 0012= 110 Yo tomo 1 de A
0 2 0002=010 Tomas 1 de C
0 2 1 0112= 310 La estrategia de juego normal sería tomar 1 de B, dejando un número uniforme (2)
montones de tamaño 1. Para jugar malétera, tomo todo el montón de B, para dejar un extraño
número (1) de montones de tamaño 1.
0 1 0012= 110 Tomas 1 de C y pierdes.

Prueba de la fórmula ganadora

C. Bouton demostró la solidez de la estrategia óptima descrita anteriormente.

Teorema. En un juego normal de Nim, el jugador que hace el primer movimiento tiene una estrategia ganadora si y solo si la suma nim de los tamaños de los montones no es cero. De lo contrario, el segundo jugador tiene una estrategia ganadora.

Prueba: Observe que la suma nim (⊕) obedece las leyes usuales de suma asociativa y conmutativa (+) y también satisface una propiedad adicional, x ⊕ x = 0.

Sean x₁,..., x_n los tamaños de los montones antes de un movimiento, y y₁,..., y_n los tamaños correspondientes después de un movimiento. Sean s = x₁ ⊕... ⊕ x_n y t = y₁ ⊕... ⊕ y_n. Si el movimiento fue en el montón k, tenemos x_i = y_i para todo i ≠ k, y x_k > y_k. Por las propiedades de ⊕ mencionadas anteriormente, tenemos

 t = 0 ⊕ t= s ⊕ s ⊕ t= s ⊕x1 ⊕ xn⊕Sí.1 ⊕ Sí.n)
= s ⊕x1 ⊕ Sí.1⊕xn ⊕ Sí.n)
= s ⊕ 0 ⊕xk ⊕ Sí.k⊕ 0 ⊕
= s ⊕ xk ⊕ Sí.k(*) t = s ⊕ xk ⊕ Sí.k.

El teorema se sigue por inducción sobre la duración del juego a partir de estos dos lemas.

Lema 1. Si s = 0, entonces t ≠ 0 sin importar qué movimiento se haga.

Prueba: Si no hay movimiento posible, entonces el lema es vacuamente verdadero (y el primer jugador pierde el juego normal por definición). De lo contrario, cualquier movimiento en el montón k producirá t = x_k ⊕ y_k de (*). Este número es distinto de cero, ya que x_k ≠ y_k.

Lema 2. Si s ≠ 0, es posible hacer un movimiento tal que t = 0.

Prueba: Sea d la posición del bit distinto de cero más a la izquierda (el más significativo) en la representación binaria de s y elija k tal que el désimo bit de x_k también es distinto de cero. (Tal k debe existir, ya que de lo contrario el désimo bit de s sería 0). Luego, haciendo y_k = s ⊕ x_k, afirmamos que y_k < x_k: todos los bits a la izquierda de d son iguales en x_k y y_k, el bit d disminuye de 1 a 0 (disminuyendo el valor en 2^d ), y cualquier cambio en los bits restantes ascenderá a un máximo de 2^d−1. Por lo tanto, el primer jugador puede hacer un movimiento tomando objetos x_k − y_k del montón k , entonces

t = s ⊕ xk ⊕ Sí.k (por (*))
= s ⊕ xk ⊕s ⊕ xk)
= 0.

La modificación para el juego misère se demuestra observando que la modificación surge primero en una posición que tiene solo un montón de tamaño 2 o más. Nótese que en tal posición s ≠ 0, y por lo tanto esta situación tiene que darse cuando es el turno del jugador que sigue la estrategia ganadora. La estrategia de juego normal es que el jugador reduzca esto al tamaño 0 o 1, dejando un número par de montones con el tamaño 1, y la estrategia misère es hacer lo contrario. A partir de ese momento, todos los movimientos son forzados.

Variaciones

El juego de la resta

Juego de resta interactiva: Los jugadores toman turnos eliminando 1, 2 o 3 objetos de una piscina inicial de 21 objetos. El jugador que toma el último objeto gana.

En otro juego que se conoce comúnmente como Nim (pero es mejor llamarlo juego de resta), se impone un límite superior a la cantidad de objetos que se pueden eliminar en un turno. En lugar de eliminar arbitrariamente muchos objetos, un jugador solo puede eliminar 1 o 2 o... o k a la vez. Este juego se juega comúnmente en la práctica con un solo montón.

El análisis de Bouton se traslada fácilmente a la versión general de varios montones de este juego. La única diferencia es que, como primer paso, antes de calcular las Nim-sums, debemos reducir los tamaños de los montones módulo k + 1. Si esto hace que todos los montones sean de tamaño cero (en misère play), el movimiento ganador es tomar k objetos de uno de los montones. En particular, en un juego ideal de un solo montón de n objetos, el segundo jugador puede ganar si y solo si

0(modelo)k+ 1) (en juego normal), o

1(modelo)k+ 1) (en el juego de misères).

Esto se deriva del cálculo de la secuencia nim de S(1,2,...,k),

0.123...... k0123...... k0123⋯ ⋯ =0Í Í .123...... kÍ Í ,{displaystyle 0.123ldots k0123ldots k0123dots ={dot {0}.123ldots {dot {}}}}

de donde la estrategia anterior se deriva del teorema de Sprague-Grundy.

El juego 21

El juego "21" se juega como un juego misère con cualquier número de jugadores que se turnan para decir un número. El primer jugador dice "1" y cada jugador por turno aumenta el número en 1, 2 o 3, pero no puede exceder de 21; el jugador obligado a decir "21" pierde Esto se puede modelar como un juego de resta con un montón de 21–n objetos. La estrategia ganadora para la versión de dos jugadores de este juego es decir siempre un múltiplo de 4; entonces se garantiza que el otro jugador finalmente tendrá que decir 21; así que en la versión estándar, en la que el primer jugador abre con '1', comienza con una jugada perdedora.

El juego 21 también se puede jugar con diferentes números, por ejemplo, "Suma como máximo 5; pierde en el 34'.

Un juego de muestra de 21 en el que el segundo jugador sigue la estrategia ganadora:

Número de jugador
1 1 1
2 4
1 5, 6 o 7
2 8
1 9, 10 o 11
2 12
1 13, 14 o 15
2 16
1 17, 18 o 19
2 20
1 21

El juego de los 100

Una versión similar es el "100 game": dos jugadores comienzan desde 0 y alternativamente agregan un número del 1 al 10 a la suma. El jugador que llega a 100 gana. La estrategia ganadora es llegar a un número en el que los dígitos son posteriores (por ejemplo, 01, 12, 23, 34,...) y controlar el juego saltando a través de todos los números de esta secuencia. Una vez que un jugador llega a 89, el oponente solo puede elegir números del 90 al 99, y la siguiente respuesta puede ser, en cualquier caso, 100.

Una regla de varios montones

En otra variación de Nim, además de eliminar cualquier cantidad de objetos de un solo montón, se permite eliminar la misma cantidad de objetos de cada montón.

Nim circular

Otra variación de Nim es 'Circular Nim', en la que se coloca cualquier cantidad de objetos en un círculo y dos jugadores eliminan alternativamente uno, dos o tres objetos adyacentes. Por ejemplo, comenzando con un círculo de diez objetos,

...

se toman tres objetos en el primer movimiento

_...

luego otros tres

_

entonces uno

_

pero entonces no se pueden eliminar tres objetos en un solo movimiento.

El juego de Grundy

En el juego de Grundy, otra variación de Nim, se colocan varios objetos en un montón inicial y dos jugadores dividen alternativamente un montón en dos montones no vacíos de diferentes tamaños. Así, seis objetos pueden dividirse en montones de 5+1 o 4+2, pero no de 3+3. El juego de Grundy se puede jugar como misère o como juego normal.

Codiciosa Nim

Greedy Nim es una variación en la que los jugadores están restringidos a elegir piedras del montón más grande. Es un juego imparcial finito. Greedy Nim Misère tiene las mismas reglas que Greedy Nim, pero aquí el último jugador capaz de hacer un movimiento pierde.

Sea el mayor número de piedras en un montón m y el segundo mayor número de piedras en un montón sea n. Sea p_m el número de pilas que tienen m piedras y p_n sea el número de pilas que tienen n piedras. Luego hay un teorema de que las posiciones del juego con p_m son incluso posiciones P. Este teorema se puede demostrar considerando las posiciones donde p_m es impar. Si p_m es mayor que 1, se pueden quitar todas las piedras de esta pila para reducir p _m por 1 y el nuevo p_m será par. Si p_m = 1 (es decir, el montón más grande es único), hay dos casos:

• Si p_n es extraño, el tamaño del mayor montón se reduce a n (así que ahora el nuevo p_m es incluso).
• Si p_n es incluso, el mayor montón es eliminado por completo, dejando un número de montones más grandes.

Por lo tanto, existe un movimiento a un estado donde p_m es par. Por el contrario, si p_m es par, si cualquier movimiento es posible (p_m ≠ 0), entonces debe llevar el juego a un estado donde p_m es impar. La posición final del juego es par (p_m = 0). Por lo tanto, cada posición del juego con par p_m debe ser una posición P.

Índice-k Nim

Una generalización de Nim de múltiples saltos fue llamada "Nimk{displaystyle {fnK}"o "index-k"Nom de E. H. Moore, quien lo analizó en 1910. In index-k Nim, en lugar de quitar objetos de sólo un montón, los jugadores pueden eliminar objetos de al menos uno pero hasta k diferentes montones. El número de elementos que pueden eliminarse de cada monto puede ser arbitrario o limitado a la mayoría de los casos r elementos, como en el "juego de substracción" arriba.

La estrategia ganadora es la siguiente: al igual que en Nim de varios montones ordinarios, se considera la representación binaria de los tamaños de los montones (o módulos de tamaños de montones r + 1). En Nim ordinario, uno forma la suma XOR (o suma módulo 2) de cada dígito binario, y la estrategia ganadora es hacer que cada suma XOR sea cero. En la generalización a index-k Nim, se forma la suma de cada dígito binario módulo k + 1.

Nuevamente, la estrategia ganadora es moverse de manera que esta suma sea cero para cada dígito. De hecho, el valor así calculado es cero para la posición final, y dada una configuración de montones para los cuales este valor es cero, cualquier cambio de como máximo k montones hará que el valor sea distinto de cero. Por el contrario, dada una configuración con un valor distinto de cero, uno siempre puede tomar como máximo k montones, elegidos cuidadosamente, de modo que el valor sea cero.

Construyendo Nim

Construir a Nim es una variante de Nim en la que los dos jugadores primero construyen el juego de Nim. Dadas n piedras y s pilas vacías, los jugadores, alternando turnos, colocan exactamente una piedra en una pila de su elección. Una vez que se colocan todas las piedras, comienza un juego de Nim, comenzando con el siguiente jugador que movería. Este juego se denota BN(n,s).

Nim de dimensiones superiores

n-d Nim se juega en un k1× × ⋯ ⋯ × × kn{displaystyle k_{1}times dots times k_{n} tablero, donde cualquier número de piezas continuas se puede quitar de cualquier hiper-row. La posición inicial es generalmente el tablero completo, pero se permiten otras opciones.

Gráfico Nim

El tablero inicial es un gráfico desconectado y los jugadores se turnan para eliminar los vértices adyacentes.

Caramelo Nim

Candy Nim es una versión del juego normal de Nim en el que los jugadores intentan lograr dos objetivos al mismo tiempo: tomar el último objeto (en este caso, dulces) y tomar la mayor cantidad de dulces al final del juego.

Wordnim

Wordnim es la versión verbal de Nim en la que los jugadores forman palabras a partir de conjuntos iniciales o series de letras hasta que no queda ninguna o no se puede formar ninguna palabra legítima.