Juego de Nim y el Teorema de Sprague–Grundy

El juego de Nim: análisis completo

Nim. Se tienen $k$ montones de fichas con tamaños $n_1, n_2, \ldots, n_k$. En cada turno, el jugador elige un montón y retira al menos una ficha de ese montón (puede vaciarlo). El jugador que tome la última ficha gana (convención normal play).

Teorema de Bouton (1902). La posición $(n_1, n_2, \ldots, n_k)$ es una P-posición si y solo si $n_1 \oplus n_2 \oplus \cdots \oplus n_k = 0$, donde $\oplus$ denota el XOR bit a bit (suma en $\mathbb{F}_2$ de las representaciones binarias).

Demostración. Verificamos las dos condiciones de la dicotomía P/N: (1) Si $n_1 \oplus \cdots \oplus n_k = 0$ entonces todo movimiento (reducir algún $n_i$ a $n_i'$ con $n_i' < n_i$) lleva a una posición con XOR $\ne 0$ (pues cambiar $n_i$ a $n_i'$ cambia el XOR). (2) Si $n_1 \oplus \cdots \oplus n_k \ne 0$, existe un movimiento que lleva a XOR $= 0$: sea $b$ el bit más significativo de $n_1 \oplus \cdots \oplus n_k$; algún $n_i$ tiene el bit $b$ igual a 1, y se puede reducir $n_i$ a $n_i' = n_i \oplus (n_1 \oplus \cdots \oplus n_k) < n_i$ (lo cual da XOR total $= 0$). Luego la posición inicial es P iff XOR $= 0$.

La estrategia ganadora desde una N-posición: siempre mover al único $n_i$ tal que $n_i \oplus (\text{XOR total})$ da XOR total $= 0$ en la nueva posición. Esta estrategia está bien definida y el juego termina en tiempo finito.

El nimero (valor de Grundy)

Sea $G$ un juego combinatorio y $v$ una posición. El valor de Grundy (o nimero) $\mathcal{G}(v)$ se define recursivamente:

$\mathcal{G}(v) = \text{mex}\{\mathcal{G}(w) : v \to w\}$

donde $\text{mex}(S)$ (minimum excludant) es el menor entero no negativo que no está en $S$. Para posiciones terminales (sin sucesores), $\mathcal{G}(v) = \text{mex}(\emptyset) = 0$.

Propiedades fundamentales. (1) $v$ es P-posición si y solo si $\mathcal{G}(v) = 0$. (2) Si $\mathcal{G}(v) = g > 0$, el jugador en turno puede moverse a cualquier posición con nimero $0, 1, \ldots, g-1$ (pues mex garantiza que cada uno de esos valores es alcanzable). (3) El nimero de un montón de Nim de tamaño $n$ es simplemente $n$ (pues desde $n$ se puede alcanzar exactamente $0, 1, \ldots, n-1$).

El nimero es la cantidad que "mide" cuán ganadora es una posición, no solo si es ganadora o no. Esta granularidad es esencial para analizar sumas de juegos.

El Teorema de Sprague–Grundy

Suma de juegos. Dados dos juegos $G_1$ y $G_2$, su suma $G_1 + G_2$ es el juego en que en cada turno el jugador elige uno de los dos juegos y hace un movimiento en él. El juego termina cuando no hay movimientos disponibles en ninguno de los dos.

Teorema de Sprague-Grundy. El nimero de la suma de dos juegos es el XOR de sus nimeros:

$\mathcal{G}(G_1 + G_2) = \mathcal{G}(G_1) \oplus \mathcal{G}(G_2)$.

Demostración. Sea $g_1 = \mathcal{G}(G_1)$, $g_2 = \mathcal{G}(G_2)$, $g = g_1 \oplus g_2$. Debemos mostrar $\mathcal{G}(G_1 + G_2) = g$, es decir $g = \text{mex}\{\mathcal{G}(G_1' + G_2) : G_1 \to G_1'\} \cup \{\mathcal{G}(G_1 + G_2') : G_2 \to G_2'\}$. Hay dos cosas a probar: (i) $g$ no es alcanzable (asegura $\text{mex} \ne g_0$ para $g_0 < g$ o da $g_0 = g$ no excluido); más precisamente, que $g$ no pertenece al conjunto de los nimeros alcanzables. (ii) Todo valor $h < g$ es alcanzable. Para (i): si $G_1 \to G_1'$ con $\mathcal{G}(G_1') = h$, entonces $h \oplus g_2 \ne g_1 \oplus g_2 = g$ (pues $h \ne g_1$); luego $\mathcal{G}(G_1' + G_2) = h \oplus g_2 \ne g$. Similarmente para $G_2$. Para (ii): dado $h < g = g_1 \oplus g_2$, sea $b$ el bit más alto en que $h$ y $g$ difieren. Podemos ajustar $g_1$ o $g_2$ a un valor $g_i'$ con $g_i' \oplus g_{3-i} = h$ y $g_i' < g_i$ (argumento idéntico al de Nim). Luego $h$ es alcanzable.

Corolario. Todo juego combinatorio es equivalente a un único montón de Nim de tamaño $\mathcal{G}(v)$. La suma de $k$ juegos tiene nimero $\mathcal{G}(G_1) \oplus \cdots \oplus \mathcal{G}(G_k)$, y es P-posición iff este XOR es 0. El Teorema de Sprague-Grundy reduce el análisis de cualquier suma de juegos al cálculo de nimeros individuales y una operación XOR.

Cálculo de nimeros: ejemplos sistemáticos

**Juego de resta $\{1,2,3\}$.** Desde $n$ fichas, se pueden tomar 1, 2 o 3. Los nimeros: $\mathcal{G}(0) = 0$, $\mathcal{G}(1) = \text{mex}\{0\} = 1$, $\mathcal{G}(2) = \text{mex}\{0,1\} = 2$, $\mathcal{G}(3) = \text{mex}\{0,1,2\} = 3$, $\mathcal{G}(4) = \text{mex}\{1,2,3\} = 0$, $\mathcal{G}(5) = \text{mex}\{0,2,3\} = 1$, ... El patrón es $\mathcal{G}(n) = n \bmod 4$. Luego la suma de varios juegos de resta $\{1,2,3\}$ con montones $n_1, \ldots, n_k$ tiene nimero $(n_1 \bmod 4) \oplus \cdots \oplus (n_k \bmod 4)$.

Juego de Nim en grafos (Vertex Geography). Una ficha sobre un grafo $G$ inicia en $v_0$; los jugadores mueven la ficha a lo largo de aristas no visitadas. El nimero de cada posición $(v, \text{aristas usadas})$ se calcula recursivamente. Para grafos de caminos, el nimero es la longitud del camino más largo desde $v$ (paridad relevante). Para grafos generales, el cálculo puede ser complejo.

Hackenbush. En Hackenbush, hay "palitos" (aristas) conectados al suelo; el jugador elige un palito, lo borra, y toda componente desconectada del suelo cae. El nimero de un bambú (camino de longitud $n$ conectado al suelo) es $n$. El nimero de un árbol es la suma XOR de los nimeros de sus ramas. El nimero de componentes desconectadas es XOR de los nimeros de las componentes. Este resultado permite calcular el nimero de cualquier posición de Hackenbush como XOR de nimeros de árboles y ciclos.

Sprague-Grundy y Nim misère. En la variante misère (el que toma la última ficha pierde), la estrategia óptima difiere de normal play solo en el endgame: la regla es "sigue la estrategia de Nim normal hasta que queden solo montones de tamaño 1, y entonces invierte: si hay un número impar de montones de tamaño 1, pasa; si hay un número par, toma uno". Esta regla da la estrategia óptima para Nim misère, pero la generalización al Teorema de Sprague-Grundy misère para juegos arbitrarios es mucho más compleja (la teoría de misère de Sprague-Grundy fue desarrollada por Grundy-Smith y Berlekamp-Conway-Guy, y es significativamente más difícil).

Juegos compuestos en IMO: aplicaciones del Teorema de Sprague–Grundy

En IMO y IMO Shortlist, los juegos que aparecen raramente son Nim puro; lo usual es que el juego tenga una estructura que requiere calcular nimeros de componentes y combinarlos con XOR.

Señales para usar Sprague-Grundy. (1) El juego consiste en varias partes independientes (varias pilas, varias fichas sobre tableros distintos, varias instancias del mismo subjuego). (2) Las partes se juegan simultáneamente (en cada turno el jugador elige una parte y mueve en ella). (3) El enunciado pide quién gana el juego completo dados los tamaños iniciales, o pide la estrategia explícita.

Ejemplo IMO Shortlist. Un juego con $n$ fichas en un tablero lineal $\{0, 1, \ldots, N\}$: cada ficha puede moverse a la izquierda, y dos fichas no pueden ocupar la misma casilla. Este juego es equivalente a Nim con montones de tamaño iguales a los "espacios" entre fichas. El análisis usa el Teorema de Sprague-Grundy aplicado a los subjuegos (espacios) independientes.

Cuidado: juegos no acíclicos. Si el juego tiene ciclos (el estado puede repetirse), la definición de nimero via mex no es directamente aplicable (el proceso podría no terminar). En esos casos, se usa la teoría de juegos loopy o se restringe el análisis a posiciones que forman un DAG.

El dominio del Teorema de Sprague-Grundy permite al estudiante convertir cualquier problema de juego compuesto en un problema de XOR, reduciendo el análisis combinatorio a un cálculo algebraico sobre $\mathbb{F}_2$. Esto es precisamente la conexión entre el Capítulo 3 (álgebra lineal sobre $\mathbb{F}_2$) y la teoría de juegos.