Nim es un juego matemático de estrategia en el que dos jugadores se turnan para retirar (o "quitar") objetos de distintos montones o pilas. En cada turno, un jugador debe retirar al menos un objeto y puede retirar cualquier cantidad de objetos siempre que todos provengan del mismo montón o pila. Dependiendo de la versión que se juegue, el objetivo del juego es evitar tomar el último objeto o tomar el último objeto.
Nim es fundamental para el teorema de Sprague-Grundy , que esencialmente dice que cada juego imparcial es equivalente a un juego nim con una sola pila.
Se han jugado variantes del nim desde la antigüedad. [1] Se dice que el juego se originó en China —se parece mucho al juego chino de jiǎn-shízi (捡石子), o "recoger piedras" [2] — pero el origen es incierto; las primeras referencias europeas al 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, [3] pero los orígenes del nombre nunca fueron explicados por completo. El Oxford English Dictionary deriva el nombre del verbo alemán nimm , que significa "tomar".
En la Feria Mundial de Nueva York de 1939, Westinghouse exhibió una máquina, la Nimatron , que jugaba al nim. [4] Desde el 11 de mayo hasta el 27 de octubre de 1940, solo unas pocas personas pudieron vencer a la máquina en ese período de seis meses; si lo hacían, se les presentaba una moneda que decía "Nim Champ". [5] También fue uno de los primeros juegos electrónicos computarizados de la historia. Ferranti construyó una computadora para jugar al nim que se exhibió en el Festival de Gran Bretaña en 1951. En 1952, Herbert Koppel, Eugene Grant y Howard Bailer, ingenieros de la WL Maxson Corporation, desarrollaron una máquina que pesaba 23 kilogramos (50 libras) que jugaba al nim contra un oponente humano y ganaba regularmente. [6] Se ha descrito una máquina para jugar al nim hecha con tinkertoys . [7]
El juego del nim fue el tema de la columna Mathematical Games de Martin Gardner de febrero de 1958 en Scientific American . Una versión del nim se juega (y tiene importancia simbólica) en la película de la nouvelle vague francesa El año pasado en Marienbad (1961). [8]
El Nim se juega típicamente como un juego de misère , en el que el jugador que toma el último objeto pierde. El Nim también se puede jugar como un juego de "juego normal" en el que el jugador que toma el último objeto gana. Tanto en el juego normal como en un juego de misère, cuando hay exactamente un montón con al menos dos objetos, el jugador que toma el siguiente puede ganar fácilmente. Si esto elimina todos o todos los objetos menos uno 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 haría el jugador 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 de misère), entonces el otro jugador toma el último.
El juego normal se juega entre dos jugadores y se juega con tres montones de cualquier cantidad de objetos. Los dos jugadores se turnan para tomar cualquier cantidad de objetos de cualquiera de los montones. El objetivo es ser el último en tomar un objeto. En cambio, en el juego misère, el objetivo es asegurarse de 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 , quienes comienzan con montones de tres, cuatro y cinco objetos.
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, pueda ocupar una de las posiciones más pequeñas. Solo el último movimiento cambia entre la miseria y el juego normal.
Para las generalizaciones, n y m pueden ser cualquier valor > 0 y pueden ser iguales.
El nim de juego normal (o más precisamente el sistema de nimbers ) es fundamental para el teorema de Sprague-Grundy , que esencialmente 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 imparciales de juego normal se les puede asignar un valor nim, ese no es el caso según la convención de misère. Solo se pueden jugar juegos mansos utilizando la misma estrategia que misère nim.
Nim es un caso especial de un juego poset donde el poset consiste en cadenas disjuntas (los montones).
El gráfico de evolución del juego de nim con tres montones es el mismo que las tres ramas del gráfico de evolución del autómata Ulam–Warburton . [9]
Nim se ha resuelto matemáticamente para cualquier número de montones y objetos iniciales, y hay una forma fácilmente calculada de determinar qué jugador ganará y qué movimientos ganadores están abiertos a ese jugador.
La clave de la teoría de juegos es la suma digital binaria de los tamaños de los montículos, es decir, la suma (en binario) despreciando todos los acarreos de un dígito a otro. Esta operación también se conoce como " xor bit a bit " o "suma vectorial sobre GF (2) " (suma bit a bit módulo 2). Dentro de la teoría de juegos combinatorios se la suele llamar nim-sum , como se llamará aquí. La nim-sum de x e y se escribe x ⊕ y para distinguirla de la suma ordinaria, x + y . Un ejemplo del cálculo con montículos de tamaño 3, 4 y 5 es el siguiente:
Decimal binario 011 2 3 10 Montón A 100 2 4 10 Montón B 101 2 5 10 Montón C --- 010 2 2 10 La suma mínima 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 potencias distintas de 2, cancelar pares de potencias iguales y luego sumar lo que queda:
3 = 0 + 2 + 1 = 2 1 Montón A4 = 4 + 0 + 0 = 4 Montón B5 = 4 + 0 + 1 = 4 1 Montón C-------------------------------------------------- ------------------2 = 2 ¿Qué queda después de cancelar 1 y 4?
En un juego normal, la estrategia ganadora es terminar cada movimiento con una suma nim de 0. Esto siempre es posible si la suma nim no es cero antes del movimiento. Si la suma nim es cero, entonces el siguiente jugador perderá si el otro jugador no comete un error. Para averiguar qué movimiento hacer, sea X la suma nim de todos los tamaños de montón. Encuentre un montón donde la suma nim de X y el tamaño del montón sea menor que el tamaño del montón; la estrategia ganadora es jugar en dicho montón, reduciendo ese montón a la suma nim de su tamaño original con X. En el ejemplo anterior, tomando la suma nim 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
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 particular y sencillo, si sólo quedan dos montones, la estrategia consiste en reducir la cantidad de objetos en el montón más grande para que los montones sean iguales. Después de eso, sin importar qué movimiento haga el oponente, el jugador puede hacer el mismo movimiento en el otro montón, garantizando así que tomará el último objeto.
Cuando se juega como un juego de miseria, la estrategia nim es diferente solo cuando la jugada normal dejaría solo montones de tamaño uno. En ese caso, la jugada correcta es dejar un número impar de montones de tamaño uno (en el juego normal, la jugada correcta sería dejar un número par de esos montones).
Estas estrategias para el juego normal y el juego de miseria 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 quita todos los objetos (o todos menos uno) del montón que tiene dos o más, de modo que ningún montón tendrá más de un objeto (en otras palabras, todos los montones restantes tienen exactamente un objeto cada uno), por lo que los jugadores se ven obligados a quitar alternativamente exactamente un objeto hasta que el juego termina. 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 de miseria, 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 miseria con montones de tamaños tres, cuatro y cinco, la estrategia se aplicaría así:
La solidez de la estrategia óptima descrita anteriormente fue demostrada por C. Bouton.
Teorema . En un juego de nim normal, el jugador que realiza 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: Nótese que la suma nim (⊕) obedece las leyes asociativas y conmutativas habituales de la adición (+) y también satisface una propiedad adicional, x ⊕ x = 0.
Sean x 1 , ..., x n los tamaños de los montones antes de un movimiento, e y 1 , ..., y n los tamaños correspondientes después de un movimiento. Sean s = x 1 ⊕ ... ⊕ x n y t = y 1 ⊕ ... ⊕ 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
El teorema se deduce por inducción de la duración del juego a partir de estos dos lemas.
Lema 1. Si s = 0, entonces t ≠ 0 sin importar qué movimiento se realice.
Demostración: Si no hay movimiento posible, entonces el lema es vacuamente verdadero (y el primer jugador pierde la partida normal por definición). De lo contrario, cualquier movimiento en el montón k producirá t = x k ⊕ y k a partir de (*). Este número no es cero, ya que x k ≠ y k .
Lema 2. Si s ≠ 0, es posible realizar un movimiento tal que t = 0.
Demostración: Sea d la posición del bit distinto de cero más a la izquierda (más significativo) en la representación binaria de s , y elijamos k de modo que el d ésimo bit de x k también sea distinto de cero. (Debe existir un k así , ya que de lo contrario el d ésimo bit de s sería 0). Entonces, dejando y k = s ⊕ x k , afirmamos que y k < x k : todos los bits a la izquierda de d son iguales en x k e 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 lo sumo a 2 d −1. El primer jugador puede, por tanto, realizar un movimiento tomando x k − y k objetos del montón k , luego
t = s ⊕ x k ⊕ y k (por (*)) = s ⊕ x k ⊕ ( s ⊕ x k ) = 0.
La modificación para el juego misère se demuestra al notar 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 surgir cuando es el turno del jugador que sigue la estrategia ganadora. La estrategia de juego normal es que el jugador reduzca esto a tamaño 0 o 1, dejando un número par de montones con tamaño 1, y la estrategia misère es hacer lo opuesto. A partir de ese punto, todos los movimientos son forzados.
En otro juego conocido comúnmente como nim (pero que se llama mejor el juego de la resta ), se impone un límite superior a la cantidad de objetos que se pueden eliminar en un turno. En lugar de eliminar una cantidad arbitraria de 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 este juego con múltiples montones. La única diferencia es que, como primer paso, antes de calcular las sumas mínimas, 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 un juego misère), la jugada ganadora es tomar k objetos de uno de los montones. En particular, en un juego ideal, a partir de un único montón de n objetos, el segundo jugador puede ganar si y solo si
Esto se desprende del cálculo de la secuencia nim de S (1, 2, ..., k ),
de donde se deduce la estrategia anterior por el teorema de Sprague-Grundy .
El juego "21" se juega como un juego de 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 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 tendrá que decir finalmente 21; por lo tanto, en la versión estándar, en la que el primer jugador comienza con "1", comienza con un movimiento perdedor.
El juego 21 también se puede jugar con diferentes números, por ejemplo, "Sumar como máximo 5; perder con 34".
Un juego de muestra de 21 en el que el segundo jugador sigue la estrategia ganadora:
Una versión similar es el "juego del 100": dos jugadores empiezan desde el 0 y van añadiendo alternativamente un número del 1 al 10 a la suma. El jugador que llega a 100 gana. La estrategia ganadora consiste en llegar a un número en el que los dígitos sean consecutivos (por ejemplo, 01, 12, 23, 34,...) y controlar el juego saltando por todos los números de esta secuencia. Una vez que un jugador llega a 89, el oponente sólo puede elegir números del 90 al 99, y la siguiente respuesta puede ser en cualquier caso 100.
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.
Otra variante del nim es el "nim circular", en el que se coloca cualquier cantidad de objetos en un círculo y dos jugadores retiran alternativamente uno, dos o tres objetos adyacentes. Por ejemplo, si se empieza con un círculo de diez objetos,
. . . . . . . . . .
En el primer movimiento se toman tres objetos
_ . . . . . . . _ _
luego otros tres
_ . _ _ _ . . . _ _
entonces uno
_ . _ _ _ . . _ _ _
pero entonces no se pueden sacar tres objetos en un solo movimiento.
En el juego de Grundy , otra variante del 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. De este modo, seis objetos pueden dividirse en montones de 5+1 o 4+2, pero no de 3+3. El juego de Grundy puede jugarse en modo misère o en modo normal.
Greedy nim es una variante en la que los jugadores están limitados a elegir piedras solo de la pila más grande. [10] Es un juego imparcial finito . Greedy nim misère tiene las mismas reglas que Greedy nim, pero el último jugador capaz de hacer un movimiento pierde.
Sea m el mayor número de piedras en una pila y n el segundo mayor número de piedras en una pila . Sea p m el número de pilas que tienen m piedras y p n el número de pilas que tienen n piedras. Entonces existe un teorema que establece que las posiciones del juego con p m pares son P posiciones. [11] 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 en 1 y la nueva p m será par. Si p m = 1 (es decir, la pila más grande es única), hay dos casos:
Por lo tanto, existe un movimiento hacia 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 al 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 p m par debe ser una posición P.
Una generalización del nim multi-heap fue llamada "nim " o nim "index- k " por EH Moore , [12] quien la analizó en 1910. En el nim index- k , en lugar de eliminar objetos de un solo montón, los jugadores pueden eliminar objetos de al menos uno pero hasta k montones diferentes. El número de elementos que se pueden eliminar de cada montón puede ser arbitrario o limitado a un máximo de r elementos, como en el "juego de resta" anterior.
La estrategia ganadora es la siguiente: como en el nim multiheap ordinario, se considera la representación binaria de los tamaños de heap (o tamaños de heap módulo r + 1). En el nim ordinario se 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 al nim de índice k , se forma la suma de cada dígito binario módulo k + 1.
Nuevamente, la estrategia ganadora es mover de tal 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 la cual 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, siempre se puede tomar de como máximo k montones, cuidadosamente elegidos, de modo que el valor sea cero.
La construcción de nim es una variante de nim en la que los dos jugadores primero construyen el juego de nim. Dados n piedras y s montones vacíos, los jugadores, en turnos alternos, colocan exactamente una piedra en un montón de su elección. [13] Una vez que se colocan todas las piedras, comienza un juego de Nim, que comienza con el siguiente jugador que movería. Este juego se denota BN(n,s) .
n -d nim se juega en un tablero, en el que se puede retirar cualquier número de piezas continuas de cualquier hiperfila. La posición inicial suele ser el tablero completo, pero se permiten otras opciones. [14]
El tablero inicial es un gráfico desconectado y los jugadores se turnan para eliminar los vértices adyacentes. [15]
Candy nim es una versión del nim de juego normal en el que los jugadores intentan lograr dos objetivos al mismo tiempo: tomar el último objeto (en este caso, dulces) y tomar la máxima cantidad de dulces al final del juego. [16]
El juego matemático para dos personas nim, que muchos creen que se originó en China, es probablemente uno de los juegos más antiguos del mundo.
\quad t&=s\oplus x_{k}\oplus y_{k}\end{alineado}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c571cc93b20ce1e832a325504bd27e143df8d18)
