Nim

Nim es un juego de estrategia matemática para dos jugadores. El juego comienza con varias pilas (heaps) de objetos — tradicionalmente piedras, monedas, o emparejadores. Los jugadores toman turnos eliminando cualquier número de objetos de una sola pila (al menos uno, hasta toda la pila). En la versión estándar (juego normal), el jugador que toma el último objeto gana. En la variante misère, el jugador que se ve obligado a tomar la última pérdida del objeto. Nim es uno de los juegos más fundamentales en la teoría del juego combinatorio.

Reglas (juego normal)

1. El juego comienza con un número de pilas, cada uno que contiene uno o más objetos. Una configuración de inicio común es pilas de 3, 5 y 7.
2. Dos jugadores alternan turnos.
3. En cada vuelta, un jugador debe eliminar al menos un objeto de exactamente una pila. Pueden tomar tantos objetos como deseen de esa pila, hasta e incluyendo toda la pila.
4. El jugador que toma el último objeto de la última pila ganadora.

## Reglas (variante misère)

Lo mismo que antes, excepto el jugador que se ve obligado a tomar la última pérdida del objeto.

Estrategias

Nim-Sum (Estrategia XOR): La clave para ganar Nim es la suma digital binaria (XOR) de todos los tamaños de pila. Si el XOR de todas las pilas es 0, la posición está perdiendo para el jugador cuyo turno es (con juego perfecto por el oponente). Si el XOR no es cero, el jugador actual siempre puede hacer un movimiento que deja al oponente en una posición cero-XOR.

• Cómo calcular Nim-Sum: Convertir cada tamaño de pila en binario y XOR juntos. Por ejemplo: pilas de 3 (011), 5 (101), 7 (111) → XOR = 001 (no cero, el jugador actual puede ganar).
• #Winning Move # Para ganar de una posición XOR no cero, encontrar un montón donde la eliminación de algunos objetos hace que el XOR total sea igual a cero. Siempre hay al menos una pila así.
• Misère Strategy: Juega la misma estrategia XOR que el Nim normal, pero con una excepción: cuando todas las pilas restantes tienen el tamaño 1, tomar para dejar un número impar de pilas (forzando a su oponente para tomar el último).
• Single Pile Endgame: Si sólo queda una pila, tome toda la pila (juego normal) o todo menos uno (misère).
• Dos Pilas iguales**: Si hay exactamente dos pilas del mismo tamaño, esta es una posición perdida en el juego normal (XOR = 0). Mirror los movimientos de tu oponente hasta el final del juego.

Nim tiene orígenes antiguos, aunque la historia exacta es difícil de rastrear. Juegos que implican la eliminación de objetos de pilas han sido jugados durante siglos a través de muchas culturas. El nombre "Nim" fue acuñado por Charles L. Bouton, profesor de matemáticas en la Universidad de Harvard, que publicó el análisis matemático completo del juego en 1901 en un documento titulado "Nim, A Game with a Complete Mathematical Theory." El origen del nombre es incierto — puede provenir de la palabra alemana "nimma" (toma) o del arcaico inglés "nim" (para robar).

La visión clave de Bouton fue la estrategia ganadora basada en XOR, que demostró rigurosamente. Este fue uno de los primeros juegos para ser completamente resuelto matemáticamente, y puso las bases para el campo de la teoría del juego combinatorio. Su análisis mostró que todo el juego podría reducirse a un simple cálculo binario, haciendo de Nim una de las intersecciones más elegantes de matemáticas y juegos.

En 1939, Edward U. Condon, Willard A. Derr, y Gerald L. Tawney en Westinghouse construyeron el "Nimatron", una máquina electromecánica que jugó a Nim. Fue exhibida en la Feria Mundial de Nueva York de 1940, donde ganó alrededor del 90% de los 100.000 juegos jugados en contra, lo que lo convierte en una de las primeras máquinas de juego. En 1951, el equipo Nimrod fue construido específicamente para jugar a Nim y fue exhibido en el Festival de Gran Bretaña, convirtiéndose en uno de los primeros ejemplos de ordenadores de juego digital.

La teoría matemática de Nim, particularmente el teorema Sprague-Grundy (desarrollado por Roland Sprague en 1935 y Patrick Grundy en 1939), se convirtió en la base de la teoría combinatoria juego. El teorema muestra que cada juego imparcial (uno donde ambos jugadores tienen los mismos movimientos disponibles) es equivalente a una posición de Nim. Esto significa que la estrategia para Nim puede, en teoría, ser aplicada a cualquier juego imparcial. Nim sigue siendo un tema estándar en la educación matemática y informática y se utiliza con frecuencia para introducir estudiantes a la teoría del juego y aritmética binaria.