Jugador 1
·
Rival
·
🔢 Estado actual
Turno:—
Nim-Sum (XOR):—
Posición:—
—
📜 Historial
Sin movimientos aún…
El Nim es uno de los juegos matemáticos más antiguos y estudiados del mundo. Se trata de un juego de información perfecta para dos jugadores, en el que la suerte no existe: quien tiene la estrategia correcta, gana siempre. Su nombre probablemente proviene del alemán "nehmen" (tomar). Fue completamente resuelto matemáticamente en 1901 por Charles L. Bouton.
El juego comienza con varias filas de piedras (o palitos, monedas, objetos…). Cada fila puede tener un número distinto de piedras. El tablero más clásico es el 1-3-5-7:
En tu turno, elige una sola fila y quita de ella cualquier cantidad de piedras (al menos 1, hasta todas las que haya en esa fila).
No puedes quitar piedras de varias filas en el mismo turno. No puedes pasar turno sin quitar ninguna piedra. No puedes quitar más piedras de las que hay.
El jugador que toma la última piedra gana. (Existe la variante "misère" donde perdes si tomas la última, pero aquí jugamos la versión normal.)
Veamos una partida completa con el tablero pequeño 1-2-3. Jugadores: Tú y IA. Empiezas tú.
Decides quitar 2 piedras de la fila C. Deja 1 en C.
Estado: 1-2-1
La IA analiza y decide quitar 2 piedras de la fila B (deja 0). Estado: 1-0-1
Dos filas con 1 piedra cada una. Quitas 1 piedra de la fila A. Estado: 0-0-1
Solo queda 1 piedra en la fila C. La IA la toma. ¡La IA gana! Tomó la última piedra.
Turno 1 → Jugador A quita piedras de 1 fila → Turno 2 → Jugador B quita piedras de 1 fila → … → quien toma la última gana.
Una partida clásica 1-3-5-7 dura entre 4 y 12 turnos. El tablero pequeño 1-2-3 puede resolverse en solo 3-5 movimientos.
Toda estrategia en el Nim se reduce a un objetivo: dejar siempre el Nim-Sum en 0 después de tu jugada. Si lo consigues, cualquier movimiento del rival romperá ese equilibrio, y podrás restaurarlo. La victoria es inevitable.
Sea S = Nim-Sum actual (con S ≠ 0). Busca cualquier montón de tamaño n tal que n XOR S < n. Reduce ese montón exactamente a n XOR S.
| Montón | Decimal | Bit 2 | Bit 1 | Bit 0 |
|---|---|---|---|---|
| Fila 1 | 3 | 0 | 1 | 1 |
| Fila 2 | 5 | 1 | 0 | 1 |
| Fila 3 | 7 | 1 | 1 | 1 |
| XOR (S) | 1 | 0 | 0 | 1 |
S = 1. Buscamos fila donde n XOR 1 < n:
• Fila 1 (n=3): 3 XOR 1 = 2 ✓ (2 < 3) → Quitar 1 piedra, dejar 2
Nuevo estado: 2-5-7 → XOR = 0 ✓
Cuando todos los montones tienen 0 o 1 piedras, el juego se simplifica enormemente. La regla es:
Cuenta cuántas filas no vacías quedan. Si hay un número impar de ellas, quien mueve gana tomando hasta dejar un número par.
Si hay un montón grande y el resto son filas de 1, reduce el montón grande a 1 si el número de filas-1 es par, o a 0 si es impar.
El tablero clásico 1-3-5-7 tiene Nim-Sum = 0 (posición P), por lo que el segundo jugador tiene ventaja si juega óptimo. Sin embargo, si empiezas tú, forzar errores al rival es la táctica.
Aquí también el primer jugador pierde con juego perfecto del rival. La apertura clásica es quitar toda la fila más grande (de 8) para crear complejidad.
Nim-Sum: 3⊕4⊕5⊕6 = 7⊕5⊕6 = 4. Tienes ventaja como primer jugador. La jugada ganadora es encontrar el montón donde n XOR 4 < n:
• 3 XOR 4 = 7 ✗ | 4 XOR 4 = 0 ✓ → Vaciar la fila de 4. Nuevo estado: 3-0-5-6, XOR = 0
Una jugada frecuente con efecto psicológico: vaciar o casi vaciar el montón más grande. Aunque no siempre es la óptima, obliga al rival a recalcular desde cero y puede introducirle en error.
Una jugada automática ocurre cuando la posición es tal que solo hay una jugada que preserva XOR=0. En esos casos, no hay que calcular: la respuesta es única y forzada.
Estado: 1-1-n (dos filas con 1 piedra, una con n > 1).
• Si n es impar → XOR ≠ 0 → quita n-1 piedras del montón grande (deja 1). Nuevo: 1-1-1.
• Estado 1-1-1: XOR = 1. Tu rival deberá quitar una fila entera, dejando 1-1. Tú quitas otra → 1. Rival toma la última. ¡Tú has ganado!
Si quedan dos montones del mismo tamaño, el XOR = 0 y estás en posición P. Sea lo que sea que haga el rival (reducir el montón A a k), reduce el montón B también a k. Siempre podrás imitar: ganarás.
1. Calcula S = XOR de todos los montones.
2. Busca montón n donde n XOR S < n.
3. Reduce ese montón a n XOR S.
4. Repite cada turno.
1. Haz cualquier movimiento razonable.
2. Evita dejar 0 o 1 piedra en más de 1 fila (si puedes).
3. Reza para que el rival falle.
4. Si falla, aplica XOR → 0 inmediatamente.
El Nim pertenece a la familia de los Juegos Combinatorios Imparciales (Impartial Games). Sus propiedades formales son:
• Dos jugadores alternos
• Información perfecta (nada oculto)
• Sin azar
• Movimientos disponibles iguales para ambos (imparcial)
• Condición terminal: el que no puede mover pierde (o gana, según variante)
Toda posición es exactamente una de:
P-posición (Previous player wins): quien acaba de mover gana. El que mueve desde aquí pierde con juego perfecto.
N-posición (Next player wins): quien mueve gana con juego perfecto.
Una posición es P-posición si y solo si todos sus sucesores son N-posiciones. Es N-posición si existe al menos un sucesor que es P-posición.
La clave matemática del Nim es el XOR bit a bit (también llamado suma módulo 2 en cada bit o "suma exclusiva"). Dado un montón \(n_i\), su representación binaria es la base del cálculo.
El Nim-Sum de una posición \((n_1, n_2, \ldots, n_k)\) es:
$$S = n_1 \oplus n_2 \oplus \cdots \oplus n_k$$donde \(\oplus\) denota el XOR bit a bit. En binario, se aplica módulo 2 en cada columna de bits.
Propiedades algebraicas del XOR que hacen posible la teoría:
\(a \oplus a = 0\) (elemento neutro consigo mismo)
\(a \oplus 0 = a\) (cero es neutro)
\(a \oplus b = b \oplus a\) (conmutativa)
\((a \oplus b) \oplus c = a \oplus (b \oplus c)\) (asociativa)
El conjunto \((\mathbb{Z}_{\geq 0}, \oplus)\) forma un grupo abeliano. Esto permite "deshacer" operaciones y hace que la teoría sea matemáticamente limpia y completa.
Charles L. Bouton demostró el primer gran resultado sobre el Nim:
Una posición \((n_1, n_2, \ldots, n_k)\) en Nim es una P-posición (el jugador que va a mover pierde con juego perfecto) si y solo si:
$$n_1 \oplus n_2 \oplus \cdots \oplus n_k = 0$$Es decir, el Nim-Sum es 0. En caso contrario, es una N-posición.
Demostración (esquema):
La prueba requiere verificar tres condiciones:
La posición terminal \((0,0,\ldots,0)\) satisface \(S = 0\), y es P (el que mueve pierde porque no puede mover).
Desde toda P-posición (\(S=0\)), cualquier movimiento deja una N-posición (\(S \neq 0\)).
Desde toda N-posición (\(S \neq 0\)), existe al menos un movimiento que lleva a una P-posición (\(S=0\)).
Sea \(S \neq 0\). Sea \(b\) el bit más significativo de \(S\). Existe al menos un montón \(n_i\) cuyo bit \(b\) es 1 (si no, ese bit de \(S\) no podría ser 1). Para ese montón, \(n_i \oplus S < n_i\) (pues el bit \(b\) de \(n_i\) pasa de 1 a 0). Definimos \(n_i' = n_i \oplus S\). Si reducimos el montón \(i\) de \(n_i\) a \(n_i'\), el nuevo Nim-Sum es:
$$S' = S \oplus n_i \oplus n_i' = S \oplus n_i \oplus (n_i \oplus S) = 0 \quad \square$$El resultado más profundo de la teoría de juegos combinatorios. Generaliza el Nim a cualquier juego combinatorio imparcial.
Para cada posición \(P\) de un juego, el valor de Grundy \(G(P)\) (o nimber) se define recursivamente:
$$G(P) = \text{mex}\{G(Q) : Q \text{ es sucesor de } P\}$$donde \(\text{mex}\) (mínimo excludente) es el menor entero no negativo que no aparece en el conjunto.
Para un único montón de \(n\) piedras, los sucesores son todos los montones de 0 a n-1 piedras. Por tanto:
$$G(n) = \text{mex}\{0, 1, 2, \ldots, n-1\} = n$$El valor de Grundy de un montón de \(n\) piedras en Nim es exactamente \(n\).
El valor de Grundy de la suma de juegos es el XOR de los valores individuales:
$$G(G_1 + G_2 + \cdots + G_k) = G(G_1) \oplus G(G_2) \oplus \cdots \oplus G(G_k)$$Aplicado al Nim con montones \((n_1, \ldots, n_k)\):
$$G = n_1 \oplus n_2 \oplus \cdots \oplus n_k$$La posición es P si y solo si \(G = 0\). Esto unifica el Teorema de Bouton como caso particular.
La importancia del teorema es enorme: cualquier juego combinatorio imparcial finito es equivalente a algún montón de Nim. Los nimbers forman un cuerpo algebraico bajo XOR y multiplicación de Nim.
En la variante misère, el jugador que toma la última piedra pierde. Esto cambia sutilmente la estrategia.
La estrategia óptima en Misère Nim es:
• Si todos los montones son 0 o 1: gana el jugador que deja un número par de montones con 1 piedra.
• Si algún montón tiene ≥ 2 piedras: juega igual que en Nim normal (XOR → 0), excepto al final: cuando queda solo un montón grande, en lugar de reducirlo a 1, redúcelo a 0.
Formalmente, la condición ganadora en Misère es:
$$\begin{cases} S \neq 0 & \text{si } \max(n_i) \geq 2 \\ S = 0 & \text{si todos } n_i \leq 1 \end{cases}$$donde en ambos casos esa condición indica posición perdedora para quien mueve (al contrario del Nim normal).
Los nimbers (valores de Grundy) forman una estructura algebraica más rica que un mero grupo.
\(\alpha \oplus \beta\) es conmutativa, asociativa, con neutro 0. Todo elemento es su propio inverso: \(\alpha \oplus \alpha = 0\).
Se define recursivamente sobre potencias de 2 de Fermat. Por ejemplo: \(2 \otimes 2 = 3\), \(2 \otimes 3 = 1\). Los nimbers con estas operaciones forman un cuerpo (field).
El conjunto de todos los nimbers finitos con suma \(\oplus\) y producto de Nim \(\otimes\) es isomorfo al campo de Galois \(\text{GF}(2^{2^n})\) para cada potencia de 2. Esto conecta el Nim con la teoría de cuerpos finitos y el álgebra abstracta moderna.
$$(\mathbb{No}, \oplus, \otimes) \cong \overline{\mathbb{F}_2} \quad \text{(clausura algebraica de } \mathbb{F}_2\text{)}$$¿Cómo transformar toda esta teoría en victorias concretas?
S ← n₁ ⊕ n₂ ⊕ … ⊕ nₖ
SI S = 0: hacer cualquier movimiento (posición perdedora)
PARA CADA montón nᵢ:
SI nᵢ XOR S < nᵢ:
Reducir montón i a (nᵢ XOR S)
SALIR
VERIFICAR: nuevo S = 0 ✓
Este algoritmo es \(O(k \cdot \log(\max n_i))\) en tiempo, donde \(k\) es el número de montones. Prácticamente instantáneo para cualquier juego real.
| Posición | Nim-Sum | Tipo | Jugada |
|---|---|---|---|
| (1,2,3) | 0 | P | Cualquiera; rival gana |
| (1,3,5,7) | 0 | P | Cualquiera; rival gana |
| (2,4,6,8) | 0 | P | Cualquiera; rival gana |
| (1,2,4) | 7 | N | Vaciar fila de 4 |
| (n,n) | 0 | P | Imitar al rival |
| (1,n,n+1) | 0 | P | Cualquiera |