Ver el código de «Nim (juego)»

[[Archivo:NimGame.svg|thumb|Fósforos dispuestos en filas para un juego de Nim. Los jugadores se turnan para elegir una fila y eliminar cualquier número de fósforos.]]
'''Nim''' es un [[juego]] [[Matemáticas|matemático]] de [[Juego de estrategia|estrategia]] en el que dos jugadores se turnan para quitar (o "recortar") objetos de distintos montones. En cada turno, un jugador debe eliminar al menos un objeto y puede eliminar cualquier número 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.
Nim se juega típicamente como un ''[[Misère#Juego misère|juego de misère]]'', en el que el jugador que toma el último objeto pierde. Nim también se puede jugar como un ''juego normal,'' juego en el que el jugador que toma el último objeto gana. 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. En el juego normal o en un juego de misère, cuando el número de montones con al menos dos objetos es exactamente igual a uno, el jugador que tome 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 verán 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 Nim (o más precisamente el sistema de [[Nimber|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 Nim que produce el mismo resultado cuando se juega en paralelo con otros [[Juego imparcial|juegos imparciales]] de juego normal (ver suma disyuntiva).

Si bien a todos los [[Juego imparcial|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'' usando la misma estrategia que un ''[[misère]]'' Nim.

Nim es un caso especial de un [[juego poset]] donde el poset consiste en [[Orden total|cadenas]] disjuntas (los montones).

El gráfico de evolución del juego de Nim con tres montones es el mismo que tres ramas del gráfico de evolución del [[autómata Ulam-Warburton]].<ref>{{Cita publicación|url=http://arxiv.org/abs/1405.5942|título=Nim Fractals|apellidos=Khovanova|nombre=Tanya|apellidos2=Xiong|nombre2=Joshua|fecha=2014-05-22|publicación=arXiv:1405.5942 [math]|fechaacceso=2021-03-09}}</ref>

== Historia ==
Las variantes de Nim se han jugado desde la antigüedad.<ref>{{Cita publicación|url=https://ieeexplore.ieee.org/document/5223985|título=Context and Driving Forces in the Development of the Early Computer Game Nimbi|apellidos=Jorgensen|nombre=A. H.|fecha=2009-07|publicación=IEEE Annals of the History of Computing|volumen=31|número=3|páginas=44–53|fechaacceso=2021-03-09|issn=1934-1547|doi=10.1109/MAHC.2009.41}}</ref> Se dice que el juego se originó en [[China]] —se parece mucho al juego chino de 捡石子 ''jiǎn-shízi'', o "recoger piedras"<ref>{{Cita libro|título=Kvant selecta : Combinatorics, I|url=https://www.worldcat.org/oclc/48630680|editorial=American Mathematical Society|fecha=2001|fechaacceso=2021-03-09|isbn=0-8218-2171-7|oclc=48630680|nombre=Serge|apellidos=Tabachnikov}}</ref>— pero el origen es incierto; las primeras referencias europeas a Nim son de principios del {{siglo|XVI||s}}. 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,<ref>{{Cita publicación|url=https://www.jstor.org/stable/1967631|título=Nim, A Game with a Complete Mathematical Theory|apellidos=Bouton|nombre=Charles L.|fecha=1901|publicación=Annals of Mathematics|volumen=3|número=1/4|páginas=35–39|fechaacceso=2021-03-09|issn=0003-486X|doi=10.2307/1967631}}</ref> pero los orígenes del nombre nunca se explicaron completamente.

En la [[Exposición General de segunda categoría de Nueva York de 1939|Feria Mundial de Nueva York de 1940]], [[Westinghouse Electric (1886)|Westinghouse]] exhibió una máquina, la Nimatron, que jugaba a Nim.<ref>{{cite book|last=Flesch|first=Rudolf|title=The Art of Clear Thinking|url=https://archive.org/details/artclearthinking00rfle|year=1951|publisher=Harper and Brothers Publishers|location=New York|page=[https://archive.org/details/artclearthinking00rfle/page/n13 3]}}</ref> 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.<ref>{{Cita web|url=http://www.expomuseum.com/1939n/|título=ExpoMuseum / New York World's Fair, 1939-'40|fechaacceso=2021-03-09|sitioweb=www.expomuseum.com|fechaarchivo=24 de febrero de 2021|urlarchivo=https://web.archive.org/web/20210224130244/http://www.expomuseum.com/1939n/|deadurl=yes}}</ref><ref>{{Cita web|url=http://platinumpiotr.blogspot.com/2016/01/1940-nimatron.html|título=1940: Nimatron|fechaacceso=2021-03-09|idioma=en}}</ref> También fue uno de los primeros juegos electrónicos computarizados. Ferranti construyó una [[Nimrod (videojuego)|computadora de juego Nim]] que se exhibió en el Festival de Gran Bretaña en 1951. En 1952 Herbert Koppel, Eugene Grant y Howard Bailer, ingenieros de WL Maxon Corporation, desarrollaron una máquina que pesaba 23 kilogramos (50 libras) que jugaba a Nim contra un oponente humano y ganaba regularmente.<ref>{{Cita web|url=https://www.newyorker.com/magazine/1952/08/02/it|título=It|fechaacceso=2021-03-09|apellido=Grant|nombre=Eugene F.|sitioweb=The New Yorker|idioma=en-us}}</ref> Se ha descrito una máquina de juego Nim hecha de TinkerToy.<ref>{{cite web|url = http://harveycohen.net/papers/80-Nim_Playing_Machine.pdf|title=How to Construct NIM Playing Machine | first=Harvey A. | last=Cohen}}</ref>

El juego de Nim fue el tema de la columna ''Mathematical Games'' de [[Martin Gardner]] de febrero de 1958 en ''[[Scientific American]]''. Se reproduce una versión de Nim —y tiene una importancia simbólica— en la película francesa ''[[nouvelle vague]]'' ''[[El año pasado en Marienbad]]'' (1961).<ref>{{Cita publicación|url=https://www.jstor.org/stable/2929672|título=Games and Game Structures in Robbe-Grillet|apellidos=Morrissette|nombre=Bruce|fecha=1968|publicación=Yale French Studies|número=41|páginas=159–167|fechaacceso=2021-03-09|issn=0044-0078|doi=10.2307/2929672}}</ref>

== Juego e ilustración ==

El juego normal es entre dos jugadores y se juega con tres montones de cualquier número 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 de ''[[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 jugadores ficticios [[Alice y Bob]], que comienzan con montones de tres, cuatro y cinco objetos.

 Tamaños Movimientos
 A B C
 &nbsp;
 3 4 5 Bob toma 2 de A
 1 4 5 Alice toma 3 de C
 1 4 2 Bob toma 1 de B
 1 3 2 Alice toma 1 de B
 1 2 2 Bob toma todo el montón A, dejando dos 2
 0 2 2 Alice toma 1 de B
 0 1 2 Bob toma 1 de C dejando dos 1. ( ''En el juego de misère tomaría 2 de C saliendo (0, 1, 0).'' )
 0 1 1 Alice toma 1 de B
 0 0 1 Bob toma todo el montón de C y gana

== 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 cada turno sucesivo después debería poder hacer una de las posiciones más pequeñas. Solo el último movimiento cambia entre juego ''[[misère]]'' y normal.
{| class="wikitable" style="font-family:monospace;"
|-
!2 montones
!3 montones
!4 montones
|-
|1 1 *
|1 1 1 **
|1 1 1 1 *
|-
|2 2
|1 2 3
|1 1 n n
|-
|3 3
|1 4 5
|1 2 4 7
|-
|4 4
|1 6 7
|1 2 5 6
|-
|5 5
|1 8 9
|1 3 4 6
|-
|6 6 
|2 4 6
|1 3 5 7
|-
|7 7
|2 5 7
|2 3 4 5
|-
|8 8
|3 4 7
|2 3 6 7
|-
|9 9
|3 5 6
|2 3 8 9
|-
|n n
|4 8 12
|4 5 6 7
|-
|
|4 9 13
|4 5 8 9
|-
|
|5 8 13
|n n m m
|-
|
|5 9 12
|n n n n
|}

<nowiki>*</nowiki> Solo válido para juego normal.

<nowiki>**</nowiki> Solo válido para misere.

Para las generalizaciones, ''n'' y ''m'' puede ser cualquier valor> 0, y pueden ser el mismo.

== Teoría matemática ==

Nim se ha [[Juego resuelto|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 del montón, es decir, la suma (en binario), descuidando todos los acarreos de un dígito a otro. Esta operación también se conoce como "[[Operador a nivel de bits#XOR|xor bit a bit]]" o "suma vectorial sobre '''[[Cuerpo finito|GF]]''' (2) " (módulo 2 de adición bit a bit). Dentro de la [[teoría de juegos combinatorios]] se le suele llamar '''nim-suma''', como se llamará aquí. La nim-suma 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:

 [[Sistema binario|Binario]] [[Sistema de numeración decimal|Decimal]]
 &nbsp;
   011<sub>2</sub>    3<sub>10</sub>    Montón A
   100<sub>2</sub>    4<sub>10</sub>    Montón B
   101<sub>2</sub>    5<sub>10</sub>    Montón C
   ---
   010<sub>2</sub>    2<sub>10</sub>    La suma nim de los montones A, B, and C, 3 ⊕ 4 ⊕ 5 = 2

Un procedimiento equivalente, que a menudo es más fácil de realizar mentalmente, es expresar los tamaños del montón como sumas de potencias distintas de 2, cancelar pares de potencias iguales y luego agregar 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 Lo que queda después de cancelar 1 y 4

En el juego normal, la estrategia ganadora es terminar cada movimiento con un nim-sum de 0. Esto siempre es posible si la nim-suma 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 saber qué movimiento realizar, 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 ese montón, reduciendo ese montón a la suma mínima de su tamaño original con X. En el ejemplo anterior, tomando la suma mínima de los tamaños es {{math|1=''X''&nbsp;=&nbsp;3&nbsp;⊕&nbsp;4&nbsp;⊕&nbsp;5&nbsp;=&nbsp;2}}. Las nim-sumas de los tamaños de pila A = 3, B = 4 y C = 5 con X = 2 son
: ''A'' ⊕ ''X'' = 3 ⊕ 2 = 1      [Dado 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 el movimiento ganador es reducir el tamaño del montón A a 1 (eliminando dos objetos).

Como caso particular simple, si solo quedan dos montones, la estrategia es reducir la cantidad de objetos en el montón más grande para igualar los montones. 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 de 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 montones).

Estas estrategias para el juego normal y un 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 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 demás montones tienen 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 de 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 ''[[misère]]'' con montones de tamaños tres, cuatro y cinco, la estrategia se aplicaría así:

 A B C nim-suma 
 &nbsp;
 3 4 5 010<sub>2</sub>=2<sub>10</sub>   Saco 2 de A, dejando una suma de 000, así que ganaré.
 1 4 5 000<sub>2</sub>=0<sub>10</sub>   Sacas 2 de C
 1 4 3 110<sub>2</sub>=6<sub>10</sub>   Tomo 2 de B
 1 2 3 000<sub>2</sub>=0<sub>10</sub>   Sacas 1 de C
 1 2 2 001<sub>2</sub>=1<sub>10</sub>   Tomo 1 de A
 0 2 2 000<sub>2</sub>=0<sub>10</sub>   Sacas 1 de C
 0 2 1 011<sub>2</sub>=3<sub>10</sub>   La estrategia de juego normal sería tomar 1 de B, dejando un número par (2) montones de tamaño 1. Para jugar misère, tomo todo el montón B, para dejar un número impar (1) de montones de tamaño 1.
 0 0 1 001<sub>2</sub>=1<sub>10</sub>   Sacas 1 de C y pierdes.

=== Implementación de ejemplo ===
La estrategia anterior para un juego de misère se puede implementar fácilmente (por ejemplo, en [[Python]], a continuación).

<syntaxhighlight lang="python3">
import functools

MISERE = 'misere'
NORMAL = 'normal'

def nim(heaps, game_type):
    """Computes next move for Nim, for both game types normal and misere.

    if there is a winning move:
        return tuple(heap_index, amount_to_remove)
    else:
        return "You will lose :("

    - mid-game scenarios are the same for both game types

    >>> print(nim([1, 2, 3], MISERE))
    misere [1, 2, 3] You will lose :(
    >>> print(nim([1, 2, 3], NORMAL))
    normal [1, 2, 3] You will lose :(
    >>> print(nim([1, 2, 4], MISERE))
    misere [1, 2, 4] (2, 1)
    >>> print(nim([1, 2, 4], NORMAL))
    normal [1, 2, 4] (2, 1)

    - endgame scenarios change depending upon game type

    >>> print(nim([1], MISERE))
    misere [1] You will lose :(
    >>> print(nim([1], NORMAL))
    normal [1] (0, 1)
    >>> print(nim([1, 1], MISERE))
    misere [1, 1] (0, 1)
    >>> print(nim([1, 1], NORMAL))
    normal [1, 1] You will lose :(
    >>> print(nim([1, 5], MISERE))
    misere [1, 5] (1, 5)
    >>> print(nim([1, 5], NORMAL))
    normal [1, 5] (1, 4)
    """

    print(game_type, heaps, end=' ')

    is_misere = game_type == MISERE

    is_near_endgame = False
    count_non_0_1 = sum(1 for x in heaps if x > 1)
    is_near_endgame = (count_non_0_1 <= 1)

    # nim sum will give the correct end-game move for normal play but
    # misere requires the last move be forced onto the opponent
    if is_misere and is_near_endgame:
        moves_left = sum(1 for x in heaps if x > 0)
        is_odd = (moves_left % 2 == 1)
        sizeof_max = max(heaps)
        index_of_max = heaps.index(sizeof_max)

        if sizeof_max == 1 and is_odd:
            return "You will lose :("

        # reduce the game to an odd number of 1's
        return index_of_max, sizeof_max - int(is_odd)

    nim_sum = functools.reduce(lambda x, y: x ^ y, heaps)
    if nim_sum == 0:
        return "You will lose :("

    # Calc which move to make
    for index, heap in enumerate(heaps):
        target_size = heap ^ nim_sum
        if target_size < heap:
            amount_to_remove = heap - target_size
            return index, amount_to_remove

if __name__ == "__main__":
    import doctest
    doctest.testmod()
</syntaxhighlight>

== 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 a las leyes [[Asociatividad (álgebra)|asociativas]] y [[Conmutatividad|conmutativas]] habituales de la suma (+) y también satisface una propiedad adicional, ''x'' ⊕ ''x'' = 0.

Sean ''x''<sub>1</sub>, ...,  ''x<sub>n</sub>'' los tamaños de los montones antes de un movimiento, e ''y''<sub>1</sub>, ...,  ''y<sub>n</sub>'' los tamaños correspondientes después de un movimiento. Sea ''s'' = ''x''<sub>1</sub>  ⊕ ... ⊕  ''x<sub>n</sub>'' y ''t'' = ''y''<sub>1</sub>  ⊕ ... ⊕  ''y<sub>n</sub>''. Si el movimiento fue en el montón ''k'', tenemos ''x<sub>i</sub>'' = ''y<sub>i</sub>'' para todo ''i'' ≠ ''k'' , y ''x<sub>k</sub>'' > ''y<sub>k</sub>''. Por las propiedades de ⊕ mencionadas anteriormente, tenemos

     ''t'' = 0 ⊕ ''t''
       = ''s'' ⊕ ''s'' ⊕ ''t''
       = ''s'' ⊕ (''x''<sub>1</sub> ⊕ ... ⊕ ''x<sub>n</sub>'') ⊕ (''y''<sub>1</sub> ⊕ ... ⊕ ''y<sub>n</sub>'')
       = ''s'' ⊕ (''x''<sub>1</sub> ⊕ ''y''<sub>1</sub>) ⊕ ... ⊕ (''x<sub>n</sub>'' ⊕ ''y<sub>n</sub>'')
       = ''s'' ⊕ 0 ⊕ ... ⊕ 0 ⊕ (''x<sub>k</sub>'' ⊕ ''y<sub>k</sub>'') ⊕ 0 ⊕ ... ⊕ 0
       = ''s'' ⊕ ''x<sub>k</sub>'' ⊕ ''y<sub>k</sub>''
 &nbsp;
 (*) ''t'' = ''s'' ⊕ ''x<sub>k</sub>'' ⊕ ''y<sub>k</sub>''.

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 [[Verdad vacua|vacuo 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<sub>k</sub>'' ⊕ ''y<sub>k</sub>'' de (*). Este número es distinto de cero, ya que ''x<sub>k</sub>'' ≠ ''y <sub>k</sub>''.

'''Lema 2''': Si ''s'' ≠ 0, es posible hacer un movimiento de modo que ''t'' = 0.

''Prueba:'' 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 elija ''k'' tal que el bit ''d-''ésimo de ''x<sub>k</sub>'' sea también distinto de cero. (Tal ''k'' debe existir, ya que de lo contrario el ''d-''ésimo bit de ''s'' sería 0.) Entonces, dejando ''y<sub>k</sub>'' = ''s'' ⊕ ''x<sub>k</sub>'', afirmamos que ''y<sub>k</sub>'' < ''x<sub>k</sub>'': todos los bits a la izquierda de ''d'' son iguales en ''x<sub>k</sub>'' y ''y<sub>k</sub>'', el bit ''d'' disminuye de 1 a 0 (disminuyendo el valor en 2<sup>''d''</sup>), y cualquier cambio en los bits restantes ascenderá a 2<sup>''d''</sup>−1 como máximo. El primer jugador puede entonces hacer un movimiento tomando ''x<sub>k</sub>'' - ''y<sub>k</sub>'' objetos del montón ''k'', luego
 ''t'' = ''s'' ⊕ ''x<sub>k</sub>'' ⊕ ''y<sub>k</sub>''           (by (*))
   = ''s'' ⊕ ''x<sub>k</sub>'' ⊕ (''s'' ⊕ ''x<sub>k</sub>'')
   = 0.

La modificación para el juego ''[[misère]]'' se demuestra al señalar 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 al tamaño 0 o 1, dejando un número par de montones con el tamaño 1, y la estrategia de misère es hacer lo contrario. A partir de ese momento, todos los movimientos son forzados.

== Variaciones ==

=== The subtraction game ===

En otro juego que se conoce comúnmente como Nim (pero que se llama 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 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 (por ejemplo, con ''k''  = 3 en el juego ''Thai 21'' en ''Survivor:Tailandia'', donde apareció como un desafío de inmunidad).

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 sumas Nim debemos reducir el tamaño de los montones al [[Aritmética modular|módulo]] ''k''  + 1. Si esto hace que todos los montones de tamaño cero (en juego ''[[misère]]''), el movimiento ganador es tomar ''k'' objetos de uno de los montones. En particular, en el juego ideal de un solo montón de ''n'' objetos, el segundo jugador puede ganar [[Bicondicional|si y solo si]]
: ''n''&nbsp;≡&nbsp;0&nbsp;(mod&nbsp;''k''&nbsp;+&nbsp;1) (en juego normal), o
: ''n''&nbsp;≡&nbsp;1&nbsp;(mod&nbsp;''k''&nbsp;+&nbsp;1) (en juego ''misère'').

Esto se sigue del cálculo de la [[Teorema de Sprague-Grundy|secuencia nim]] de ''S'' (1,2, ..., ''k'' ),
: <math>0.123\ldots k0123\ldots k0123\dots = \dot0.123\ldots\dot{k}, </math>
de lo cual la estrategia anterior sigue el [[teorema de Sprague-Grundy]].

=== El juego 21 ===

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 a su vez 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 siempre decir 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 del 21 también se puede jugar con diferentes números, por ejemplo, "Suma como máximo 5; pierde con 34".

Un juego de muestra de 21 en el que el segundo jugador sigue la estrategia ganadora:
 Jugador     Número
   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 "juego 100": dos jugadores comienzan desde 0 y agregan alternativamente 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 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.

=== Regla de varios montones ===

{{See also|Juego de Wythoff}}
En otra variación de Nim, además de eliminar cualquier número de objetos de un solo montón, se permite eliminar el mismo número de objetos de cada montón.

=== Circular Nim ===

{{See also|Kayles}}
Otra variación más de Nim es 'Circular Nim', en la que cualquier número de objetos se colocan 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 sacar tres objetos de un solo movimiento.

=== Juego de Grundy ===

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

=== Greedy Nim ===

''Greedy Nim'' es una variación en la que los jugadores están restringidos a elegir piedras solo de la pila más grande.<ref name="Greedy Nim">
{{cite book | author=--- | title=Winning Ways for your Mathematical Plays | edition=2nd | publisher=A K Peters Ltd | year=2001 | volume=4 vols.}}; {{cite book|title=vol. 1|isbn=978-1-56881-130-7|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John Horton|last3=Guy|first3=Richard K.|date=2003-06-15}}; {{cite book|title=vol. 2|isbn=978-1-56881-142-0|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John Horton|last3=Guy|first3=Richard K.|date=2003-06-15}}; {{cite book|title=vol. 3|isbn=978-1-56881-143-7|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John Horton|last3=Guy|first3=Richard K.|date=2003-06-15}}; {{cite book|title=vol. 4|isbn=978-1-56881-144-4|last1=Berlekamp|first1=Elwyn R.|last2=Conway|first2=John Horton|last3=Guy|first3=Richard K.|date=2004-06-15}}
</ref> 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 ''m'' el mayor número de piedras en una pila y ''n'' el segundo número más grande de piedras en una pila . Sea ''p <sub>m</sub>'' el número de pilas que tienen ''m'' piedras y ''p <sub>n</sub>'' el número de pilas que tienen ''n'' piedras. Entonces hay un teorema de que las posiciones del juego con ''p <sub>m</sub>'' pares son posiciones ''P.''<ref name="NIM RESTRICTIONS">
{{cite journal
| author = M H Albert, R. J. Nowakowski
| title = Nim Restrictions
| year= 2004
| journal= INTEGERS: The Electronic Journal of Combinatorial Number Theory
| page = 2
| url= http://www.emis.de/journals/INTEGERS/papers/eg1/eg1.pdf
}}
</ref> Este teorema se puede demostrar considerando las posiciones donde ''p <sub>m</sub>'' es impar. Si ''p <sub>m</sub>'' es mayor que 1, se pueden quitar todas las piedras de esta pila para reducir ''p <sub>m</sub>'' en 1 y la nueva ''p'' será par. Si ''p <sub>m</sub>'' = 1 (es decir, el montón más grande es único), hay dos casos:

* Si ''p <sub>n</sub>'' es impar, el tamaño del montón más grande se reduce ''an'' (por lo que ahora el nuevo ''p <sub>m</sub>'' es par).
* Si ''p <sub>n</sub>'' es par, el montón más grande se elimina por completo, dejando un número par de montones más grandes.

Por tanto, existe un movimiento a un estado en el que ''p <sub>m</sub>'' es par. Por el contrario, si ''p <sub>m</sub>'' es par, si cualquier movimiento es posible ( ''p <sub>m</sub>'' ≠ 0), entonces debe llevar el juego a un estado en el que ''p <sub>m</sub>'' sea impar. La posición final del juego es par ( ''p <sub>m</sub>'' = 0). Por tanto, cada posición del juego con ''p <sub>m</sub>'' par debe ser una posición ''P.''

=== Index-''k'' Nim ===

Una generalización de multi-heap Nim se llamó "Nim<math>{}_k</math>" "o" index- ''k'' "Nim de E. H. Moore,<ref>Moore, E. H. ''A Generalization of the Game Called Nim''. [https://www.jstor.org/stable/1967321 Annals of Mathematics 11 (3), 1910, pp. 93–94]</ref> que 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 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 multi-montón ordinario, se considera la representación binaria de los tamaños de montón (o tamaños de montón módulo ''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, uno 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 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 un máximo de ''k'' montones, elegidos cuidadosamente, de modo que el valor se convierta en cero.

=== Building Nim ===

'''Building 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.<ref>{{cite arXiv|last1=Larsson|first1=Urban|last2=Heubach|first2=Silvia|author2-link= Silvia Heubach |last3=Dufour|first3=Matthieu|last4=Duchêne|first4=Eric|title=Building Nim|eprint=1502.04068|class=cs.DM|year=2015}}</ref> Una vez que se colocan todas las piedras, comienza un juego de Nim, comenzando con el siguiente jugador que se movería. Este juego se denota ''BN (n, s).''

=== Nim de mayor dimensión ===

''n'' -d Nim se reproduce en un tablero <math>k_1\times\dots\times k_n</math>, en el que se puede quitar cualquier número de piezas continuas de cualquier hiper-fila. La posición inicial suele ser la pensión completa, pero se permiten otras opciones.<ref>{{Cita web|url=http://poj.org/problem?id=1021|título=1021 -- 2D-Nim|fechaacceso=2021-03-09|sitioweb=poj.org}}</ref>

=== Graph Nim ===

El tablero de partida es un [[grafo]] desconectado, y los jugadores se turnan para eliminar los vértices adyacentes.

=== Candy Nim ===

Candy Nim es una versión del juego normal Nim en el que los jugadores intentan lograr dos objetivos al mismo tiempo: tomar el último objeto (en este caso, dulces) y tomar la cantidad máxima de dulces al final del juego.<ref>{{Cite web|last=Rubinstein-Salzedo|first=Simon|date=18 May 2018|title=P Play in Candy Nim|url=https://arxiv.org/pdf/1805.07019.pdf|access-date=2020-07-05}}</ref>

== Véase también ==
* [[Nim de Fibonacci]]
* [[Nimber]]
* [[Juego octal]]
* [[Estrella (teoría de juegos)]]
* [[Juego cero]]
* [[Notakto]]
* [[Chomp]]

== Referencias ==
{{listaref|2}}

== Lecturas adicionales ==
* W. W. Rouse Ball: ''Mathematical Recreations and Essays'', The Macmillan Company, 1947.
* John D. Beasley: ''The Mathematics of Games'', Oxford University Press, 1989.
* [[Elwyn Berlekamp|Elwyn R. Berlekamp]], [[John Horton Conway|John H. Conway]], y [[Richard Guy|Richard K. Guy]]: ''[[Winning Ways for your Mathematical Plays]]'', Academic Press, Inc., 1982.
* [[Manfred Eigen]] y [[Ruthild Winkler]]: ''Laws of the Game'', Princeton University Press, 1981.
* Walter R. Fuchs: ''Computers: Information Theory and Cybernetics'', Rupert Hart-Davis Educational Publications, 1971.
* G. H. Hardy y E. M. Wright: ''An Introduction to the Theory of Numbers'', Oxford University Press, 1979.
* Edward Kasner y James Newman: [[Mathematics and the Imagination]], Simon and Schuster, 1940.
* M. Kaitchik: ''Mathematical Recreations'', W. W. Norton, 1942.
* Donald D. Spencer: ''Game Playing with Computers'', Hayden Book Company, Inc., 1968.

== Enlaces externos ==
{{commons category}}
En inglés:
* [http://www.newyorker.com/archive/1952/08/02/1952_08_02_018_TNY_CARDS_000236053 50-pound computer plays Nim- The New Yorker magazine "Talk of the Town" August, 1952]{{subscription required}}
* [https://web.archive.org/web/20080820154432/http://www.cut-the-knot.org/ctk/May2001.html The hot game of Nim] – Teoría de Nim y conexión con otros juegos como [[cut-the-knot]]
* [http://www.cut-the-knot.org/nim_st.shtml Nim] and 2-dimensional [http://www.cut-the-knot.org/Games/SuperNim/SNim.shtml SuperNim] en [[cut-the-knot]]

{{Control de autoridades}}
[[Categoría:Juegos de fichas]]
[[Categoría:Juegos (teoría de juegos)]]
[[Categoría:Juegos matemáticos]]
[[Categoría:Teoría de juegos combinatorios]]
[[Categoría:Matemática recreativa]]