Hispanopedia WikiNim es un juego de combinación matemática en el que dos jugadores se turnan para retirar objetos de distintos montones o pilas. En cada turno, un jugador debe retirar al menos un objeto y puede retirar cualquier número de objetos, siempre que todos provengan del mismo montón o pila. Según la versión del juego, el objetivo es evitar tomar el último objeto o tomarlo.
Nim es fundamental para el teorema de Sprague-Grundy , que esencialmente dice que todo juego imparcial es equivalente (cuando se considera como un subjuego de un juego imparcial más grande) a un juego nim con una sola pila.
Historia
Variantes de nim se juegan desde la antigüedad. [ 1 ] Se dice que el juego se originó en China —se asemeja mucho al juego chino de jiǎn-shízǐ (捡石子), o "recoger piedras" [ 2 ] — pero su origen es incierto; las primeras referencias europeas a nim datan 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 se explicaron completamente. 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, el Nimatron , que jugaba al nim. [ 4 ] Del 11 de mayo al 27 de octubre de 1940, solo unas pocas personas lograron vencer a la máquina en ese período de seis meses; si lo hacían, recibían una moneda que decía "Nim Champ". [ 5 ] También fue uno de los primeros juegos electrónicos computarizados. Ferranti construyó una computadora que jugaba al nim y que se exhibió en el Festival de Gran Bretaña en 1951. En 1952, Herbert Koppel, Eugene Grant y Howard Baller, ingenieros de la Corporación WL Maxson, desarrollaron una máquina que pesaba 23 kilogramos (50 lb) que jugaba al nim contra un oponente humano y ganaba regularmente. [ 6 ] Se ha descrito una máquina que juega al nim hecha con Tinkertoys . [ 7 ]
El juego de nim fue el tema de la columna "Juegos matemáticos" de Martin Gardner en Scientific American en febrero de 1958. Una versión de 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 ]
Jugabilidad e ilustración
Nim se suele jugar como un juego de miseria , en el que el jugador que toma el último objeto pierde. Nim también se puede jugar como un juego "normal", en el que gana el jugador que toma el último objeto. Tanto en el juego normal como en el de miseria, 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 los objetos, o todos 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 un solo objeto hasta que termine el juego. Si el jugador deja un número par de montones distintos de cero (como haría en el juego normal), toma el último; si deja un número impar de montones (como haría en el juego de miseria), entonces el otro jugador toma el último.
El juego normal se juega entre dos jugadores 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 el juego de misère, el objetivo es obligar al oponente a tomar el último objeto restante.
El siguiente ejemplo de una partida normal se juega entre los jugadores ficticios Bob y Alice , quienes comienzan con montones de tres, cuatro y cinco objetos.
Posiciones ganadoras
La estrategia práctica para ganar en el juego de nim consiste en que un jugador lleve al otro a una de las siguientes posiciones, y en cada turno posterior debería poder lograr una de las posiciones más pequeñas. Solo la última jugada difiere entre el juego misère y el juego normal.
En las generalizaciones, n y m pueden ser cualquier valor > 0, y pueden ser iguales.
Teoría matemática
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 todo 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, esto no ocurre bajo la convención de misère. Solo los juegos mansos pueden jugarse utilizando la misma estrategia que misère nim.
Nim es un caso especial de juego de poset donde el poset consiste en cadenas disjuntas (los montones).
El grafo de evolución del juego de nim con tres montículos es el mismo que tres ramas del grafo de evolución del autómata de Ulam-Warburton . [ 9 ]
El problema de Nim se ha resuelto matemáticamente para cualquier número de montones y objetos iniciales, y existe una forma sencilla de calcular qué jugador ganará y qué movimientos ganadores están disponibles para ese jugador.
La clave de la teoría del juego reside en la suma digital binaria de los tamaños de los montones, es decir, la suma (en binario), sin tener en cuenta los acarreos entre dígitos. 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). En la teoría de juegos combinatorios, se suele denominar suma nim , como se hará aquí. La suma nim de x e y se escribe x ⊕ y para distinguirla de la suma ordinaria, x + y . Un ejemplo del cálculo con montones de tamaño 3, 4 y 5 es el siguiente:
Binario Decimal 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 de Nim de los montículos A, B y C, 3 ⊕ 4 ⊕ 5 = 2
Un procedimiento equivalente, que a menudo es más fácil de realizar mentalmente, consiste en expresar los tamaños de los montones como sumas de distintas potencias de 2, cancelar pares de potencias iguales y luego sumar lo que queda:
3 = 0 + 2 + 1 = 2 1 Montón A 4 = 4 + 0 + 0 = 4 Montón B 5 = 4 + 0 + 1 = 4 1 Montón C -------------------------------------------------------------------- 2 = 2 ¿Qué queda después de cancelar los 1 y los 4?
En el 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, 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ículo. Encuentre un montículo donde la suma nim de X y el tamaño del montículo sea menor que el tamaño del montículo; la estrategia ganadora es jugar en dicho montículo, reduciéndolo a la suma nim de su tamaño original con X. En el ejemplo anterior, tomar la suma nim de los tamaños es X = 3 ⊕ 4 ⊕ 5 = 2. Las sumas nim de los tamaños de montículo A=3, B=4 y C=5 con X=2 son
- A ⊕ X = 3 ⊕ 2 = 1 [Ya que (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 la jugada ganadora consiste en reducir el tamaño del montón A a 1 (eliminando dos objetos).
Como ejemplo sencillo, si solo quedan dos montones, la estrategia consiste en reducir la cantidad de objetos en el montón más grande para igualarlos. Después, independientemente del movimiento del oponente, el jugador puede realizar el mismo movimiento en el otro montón, asegurándose así de capturar el último objeto.
Cuando se juega como un juego de misère, la estrategia de nim difiere solo cuando el movimiento normal dejaría únicamente 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 el juego normal y el juego de 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 retira todos los objetos (o todos menos uno) del montón que tenga dos o más, de modo que ningún montón tendrá más de un objeto (es decir, todos los montones restantes tendrán exactamente un objeto cada uno), por lo que los jugadores se ven obligados a alternar la retirada de un objeto hasta que termine 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 lugar; en el juego de misère, el jugador deja un número impar de montones distintos de cero, por lo que el otro jugador toma el último lugar.
En un juego de misère con montones de tamaños tres, cuatro y cinco, la estrategia se aplicaría de la siguiente manera:
Prueba de la fórmula ganadora
La validez de la estrategia óptima descrita anteriormente fue demostrada por C. Bouton.
Teorema . En un juego 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 montículos no es cero. En caso contrario, el segundo jugador tiene una estrategia ganadora.
Prueba: Nótese que la suma nim (⊕) obedece las leyes asociativas y conmutativas usuales de la suma (+) y también satisface una propiedad adicional, x ⊕ x = 0.
Sean x 1 , ..., x n los tamaños de los montículos antes de un movimiento, e y 1 , ..., y n los tamaños correspondientes después de un movimiento. Sea s = x 1 ⊕ ... ⊕ x n y t = y 1 ⊕ ... ⊕ y n . Si el movimiento fue en el montículo k , tenemos x i = y i para todo i ≠ k , y x k > y k . Por las propiedades de ⊕ mencionadas anteriormente, tenemos
\quad t&=s\oplus x_{k}\oplus y_{k}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c571cc93b20ce1e832a325504bd27e143df8d18)
Es decir, actualizar la suma total de nimdespués de actualizar elmontón, tenemos que cancelarlo depor nim sumando cony luego nim sum en.
El teorema se deduce 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 ningún movimiento posible, entonces el lema es trivialmente cierto (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 realizar un movimiento tal que t = 0.
Demostración: Sea d la posición del bit no nulo más a la izquierda (más significativo) en la representación binaria de s , y elijamos k tal que el d -ésimo bit de x k también sea distinto de cero. (Tal k debe existir, ya que de lo contrario el d -ésimo bit de s sería 0). Entonces, 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 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á como máximo a 2 d −1. El primer jugador puede, por lo tanto, hacer un movimiento tomando x k − y k objetos del montón k , entonces
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 observar que surge por primera vez en una posición con un solo montón de tamaño 2 o más. Nótese que en tal posición s ≠ 0, por lo que esta situación debe darse cuando es el turno del jugador que sigue la estrategia ganadora. La estrategia de juego normal consiste en que el jugador reduzca este montón a tamaño 0 o 1, dejando un número par de montones de tamaño 1, mientras que la estrategia misère consiste en hacer lo contrario. A partir de ese momento, todos los movimientos son forzados.
Variaciones
El juego de resta
En otro juego conocido como nim (aunque se le denomina mejor juego de resta ), se impone un límite superior al número de objetos que se pueden eliminar en un turno. En lugar de eliminar una cantidad ilimitada de objetos, un jugador solo puede eliminar 1, 2, ... o k a la vez. Este juego se suele jugar 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 montículos. La única diferencia es que, como primer paso, antes de calcular las sumas de nim, debemos reducir los tamaños de los montículos módulo k + 1. Si esto hace que todos los montículos sean de tamaño cero (en el juego misère), el movimiento ganador es tomar k objetos de uno de los montículos. En particular, en el juego ideal desde un solo montículo de n objetos, el segundo jugador puede ganar si y solo si
- 0 = n (mod k + 1) (en juego normal), o
- 1 = n (mod k + 1) (en juego misère).
Esto se deduce del cálculo de la secuencia nim de S (1, 2, ..., k ),
de donde se deduce la estrategia anterior según el teorema de Sprague-Grundy .
El juego 21
El juego "21" se juega como un juego de la miseria 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; de esta manera, se garantiza que el otro jugador finalmente tendrá que decir 21; por lo tanto, en la versión estándar, donde el primer jugador comienza con "1", comienza con una jugada perdedora.
El juego del 21 también se puede jugar con números diferentes, por ejemplo, "Suma como máximo 5; pierde con 34".
Un ejemplo de partida de 21 en la que el segundo jugador sigue la estrategia ganadora:
El juego de los 100
Una versión similar es el "juego del 100": dos jugadores comienzan desde 0 y, alternativamente, suman un número del 1 al 10 a la suma. Gana quien llegue a 100. La estrategia ganadora consiste en alcanzar un número con dígitos 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 solo puede elegir números del 90 al 99, y la siguiente respuesta puede ser siempre 100.
Una regla de montículos múltiples
En otra variante de nim, además de poder eliminar cualquier número de objetos de un único montón, se permite eliminar el mismo número de objetos de cada montón.
Circular nim
Otra variante de nim es el "nim circular", en el que se coloca cualquier número de objetos en un círculo y dos jugadores retiran alternativamente uno, dos o tres objetos adyacentes. Por ejemplo, comenzando 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.
El juego de Grundy
En el juego de Grundy , otra variante del nim, se colocan varios objetos en un montón inicial y dos jugadores se turnan para dividirlo en dos montones no vacíos de diferente tamaño. Así, seis objetos pueden dividirse en montones de 5+1 o 4+2, pero no de 3+3. El juego de Grundy puede jugarse como misère o como juego normal.
Nim codicioso
Greedy nim es una variante en la que los jugadores están restringidos a elegir piedras solo del montón más grande. [ 10 ] Es un juego imparcial finito . Greedy nim misère tiene las mismas reglas que greedy nim, pero el último jugador que logra hacer un movimiento pierde.
Sea m el mayor número de piedras en un montón y n el segundo mayor número de piedras en un montón . Sea p m el número de montones con m piedras y p n el número de montones con n piedras. Entonces existe un teorema que establece que las posiciones de juego con p m par son posiciones P. [ 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 este montón para reducir p m en 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 impar, el tamaño del montón más grande se reduce a n (por lo que ahora el nuevo p m es par).
- Si p n es par, el montón más grande se elimina por completo, dejando un número par de montones más grandes.
Por lo tanto, existe un movimiento hacia un estado donde p m es par. Recíprocamente, si p m es par, si es posible cualquier movimiento ( 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 consiguiente, cada posición del juego con p m par debe ser una posición P.
Índice- k nim
Una generalización de nim multi-heap se denominó "nim" o "index- k " nim por EH Moore , [ 12 ] quien lo analizó en 1910. En index- k nim, 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 estar limitado a un máximo de r elementos, como en el "juego de resta" anterior.
La estrategia ganadora es la siguiente: Al igual que en el nim multi-montón ordinario, se considera la representación binaria de los tamaños de los montículos (o tamaños de los montículos 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 consiste en 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 consiste en moverse de tal manera que esta suma sea cero para cada dígito. En efecto, el valor así calculado es cero para la posición final, y dada una configuración de montículos para la cual este valor es cero, cualquier cambio de como máximo k montículos 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 montículos, cuidadosamente elegidos, de manera que el valor se convierta en cero.
Edificio nim
El nim de construcción es una variante del nim en la que los dos jugadores primero construyen el juego de nim. Dados n piedras y s pilas vacías, los jugadores, alternando turnos, colocan exactamente una piedra en una pila de su elección. [ 13 ] Una vez colocadas todas las piedras, comienza una partida de Nim, comenzando con el siguiente jugador que le toca mover. Esta partida se denota como BN(n,s) .
Nimi de dimensiones superiores
n -d nim se juega en untablero, en el que se puede eliminar cualquier número de piezas continuas de cualquier hiperfila. La posición inicial suele ser el tablero completo, pero se permiten otras opciones. [ 14 ]
Gráfico nim
El tablero inicial es un grafo desconectado, y los jugadores se turnan para eliminar vértices adyacentes. [ 15 ]
Candy nim
Candy nim es una versión del juego normal de nim en la que los jugadores intentan lograr dos objetivos al mismo tiempo: tomar el último objeto (en este caso, caramelos) y tomar la mayor cantidad de caramelos al final del juego. [ 16 ]
Véase también
Referencias
- ↑ Jorgensen, Anker Helms (2009), "Contexto y fuerzas impulsoras en el desarrollo del juego de computadora temprano Nimbi" , IEEE Annals of the History of Computing , 31 (3): 44– 53, Bibcode : 2009IAHC...31c..44J , doi : 10.1109/MAHC.2009.41 , MR 2767447 , S2CID 2833693 ,
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.
- ↑ Yaglom, IM (2001), "Dos juegos con cerillas", en Tabachnikov, Serge (ed.), Kvant Selecta: Combinatoria, I, Volumen 1 , Mundo matemático, vol. 17, Sociedad Matemática Americana , pp. 1–8 , ISBN 9780821821718
- ↑ Bouton, CL (1901–1902), "Nim, un juego con una teoría matemática completa ", Annals of Mathematics , 3 (14): 35–39 , doi : 10.2307/1967631 , JSTOR 1967631
- ↑ Flesch, Rudolf (1951). El arte de pensar con claridad . Nueva York: Harper and Brothers Publishers. pág. 3.
- ↑ Kellem, Betsy (1 de marzo de 2022). "El Nimatron" . JSTOR Daily . Archivado del original el 28 de junio de 2023. Recuperado el 28 de junio de 2023 .
- ↑ Grant, Eugene F.; Lardner, Rex (2 de agosto de 1952). "El tema de conversación de la ciudad: Eso" . The New Yorker .
- ↑ Cohen, Harvey A. "Cómo construir una máquina de juego NIM" (PDF) .
- ↑ Morrissette, Bruce (1968), "Juegos y estructuras de juego en Robbe-Grillet", Yale French Studies (41): 159– 167, doi : 10.2307/2929672 , JSTOR 2929672 Morrissette escribe que Alain Robbe-Grillet , uno de los guionistas de la película, "creía que había inventado" el juego.
- ↑ Khovanova, Tanya; Xiong, Joshua (2014). "Nim Fractals". arXiv : 1405.5942 [ math.CO ].
- ↑ Estrategias ganadoras para tus juegos matemáticos . Vol. 4 vols. (2.ª ed.). AK Peters Ltd. 2001. ;
- Berlekamp, Elwyn R.; Conway, John Horton; Guy, Richard K. (15 de junio de 2003). vol. 1. AK Peters. ISBN 978-1-56881-130-7.;
- Berlekamp, Elwyn R.; Conway, John Horton; Guy, Richard K. (15 de junio de 2003). vol. 2. AK Peters. ISBN 978-1-56881-142-0.;
- Berlekamp, Elwyn R.; Conway, John Horton; Guy, Richard K. (15 de junio de 2003). vol. 3. AK Peters. ISBN 978-1-56881-143-7.;
- Berlekamp, Elwyn R.; Conway, John Horton; Guy, Richard K. (15 de junio de 2004). vol. 4. AK Peters. ISBN 978-1-56881-144-4.
- ^ Alberto, MH; Nowakowski, RJ (2004). "Restricciones de Nim" (PDF) . Enteros . 4 G01: 2.Zbl 1081.91005 .
- ↑ Moore, EH (1910). "Una generalización del juego llamado Nim" . Anales de Matemáticas . 11 (3). [Anales de Matemáticas, Fideicomisarios de la Universidad de Princeton en nombre de los Anales de Matemáticas, Departamento de Matemáticas, Universidad de Princeton]: 93– 94. doi : 10.2307/1967321 . JSTOR 1967321 .
- ↑ Larsson, Urban; Heubach, Silvia ; Dufour, Matthieu; Duchêne, Eric (2015). "Building Nim". arXiv : 1502.04068 [ cs.DM ].
- ↑ "1021 - 2D-Nim" . Poj.org . Consultado el 9 de enero de 2019 .
- ↑ Erickson, Lindsay Anne (2011). El juego de Nim en grafos (tesis doctoral). Trabajo doctoral en matemáticas. Universidad Estatal de Dakota del Norte. hdl : 10365/32839 .
- ↑ Rubinstein-Salzedo, Simon (18 de mayo de 2018). "P Play en Candy Nim". arXiv : 1805.07019 [ math.CO ].
Lecturas adicionales
- WW Rouse Ball: Recreaciones y ensayos matemáticos , The Macmillan Company, 1947.
- John D. Beasley: Las matemáticas de los juegos , Oxford University Press, 1989.
- Elwyn R. Berlekamp, John H. Conway y Richard K. Guy: Estrategias ganadoras para sus juegos matemáticos , Academic Press, Inc., 1982.
- Manfred Eigen y Ruthild Winkler : Leyes del juego , Princeton University Press, 1981.
- Walter R. Fuchs: Computadoras: Teoría de la información y cibernética , Rupert Hart-Davis Educational Publications, 1971.
- GH Hardy y EM Wright : Introducción a la teoría de los números , Oxford University Press, 1979.
- Edward Kasner y James Newman : Matemáticas y la imaginación , Simon and Schuster, 1940.
- M. Kaitchik: Recreaciones matemáticas , WW Norton, 1942.
- Donald D. Spencer: Juegos con ordenadores , Hayden Book Company, Inc., 1968.
Enlaces externos
- " Una computadora de 23 kilos interpreta a Nim " – The New Yorker - "Talk of the Town", agosto de 1952 (se requiere suscripción)
- El popular juego de Nim : teoría de Nim y conexiones con otros juegos en cut-the-knot
- Nim y SuperNim bidimensional en el punto de corte.
- Juegos matemáticos
- teoría de juegos combinatoria
- Juegos resueltos