Análisis del Nim de Varias Pilas

Teoría

El juego del Nim es el juego imparcial por excelencia. Se juega con varias pilas de objetos, como piedras o monedas. En la versión estándar (Juego Normal), dos jugadores se turnan para quitar la cantidad de objetos que quieran de una sola pila (siempre que sea al menos uno). Gana quien haga el último movimiento. Para analizar el Nim de varias pilas usamos el Bouton's Theorem. Este dice que la estrategia ganadora depende de la suma-Nim de los tamaños de las pilas. La suma-Nim es simplemente el XOR bit a bit (OR exclusivo) de los tamaños de las pilas.

Esta técnica es clave en la teoría de juegos combinatorios porque el Sprague-Grundy theorem generaliza esta idea a cualquier juego imparcial. Si calculas la suma-Nim, puedes saber cómo está el juego: una posición P (donde gana el jugador anterior, o sea, te toca perder) ocurre cuando la suma-Nim es cero. Una posición N (donde gana el siguiente jugador, o sea, tú) ocurre cuando la suma-Nim no es cero. La estrategia usa la representación binaria de los números y te da un algoritmo exacto para ganar siempre que estés en una posición N.

La idea de usar XOR es que funciona como una suma sin acarreo. Para ganar, tienes que asegurarte de que después de tu turno, la "paridad" de las columnas binarias de las pilas esté balanceada (que sumen 0 módulo 2). Si la suma-Nim no es cero, siempre puedes encontrar un movimiento para que vuelva a ser cero. En cambio, si la suma-Nim ya es cero, cualquier movimiento que haga tu oponente va a romper el equilibrio y hará que la suma-Nim deje de ser cero.

Fórmulas Clave

Imagina que tienes $n$ pilas con tamaños $x_1, x_2, \dots, x_n$.

La Suma-Nim ($S$): $$S = x_1 \oplus x_2 \oplus \dots \oplus x_n$$ donde $\oplus$ es la operación XOR bit a bit.

Posiciones Ganadoras y Perdedoras:

• Posición P (Perdedora para el jugador actual): $S = 0$
• Posición N (Ganadora para el jugador actual): $S \neq 0$

El Movimiento Ganador: Si el estado actual tiene $S \neq 0$, elige una pila $x_k$ y cámbiala a un tamaño $x_k'$ para que la nueva suma-Nim sea 0. El tamaño que buscas es: $$x_k' = x_k \oplus S$$ Este movimiento es válido solo si $x_k' < x_k$. Siempre vas a poder encontrar una pila $x_k$ que cumpla esto.

Propiedades del XOR:

• $a \oplus a = 0$
• $a \oplus 0 = a$
• $a \oplus b = b \oplus a$ (Conmutatividad)
• $(a \oplus b) \oplus c = a \oplus (b \oplus c)$ (Asociatividad)

Demostración

Teorema (Bouton): Una posición $(x_1, \dots, x_n)$ en el Nim es una posición P (perdedora) si y solo si la suma-Nim $S = x_1 \oplus \dots \oplus x_n = 0$. De lo contrario, es una posición N (ganadora).

Demostración: Para demostrar esto, hay que checar tres propiedades de estas posiciones P y N:

1. Todas las posiciones terminales son posiciones P.
2. Desde cada posición N, hay al menos un movimiento a una posición P.
3. Desde cada posición P, cualquier movimiento posible lleva a una posición N.

Paso 1: La Posición Terminal El juego se acaba cuando todas las pilas están vacías, o sea, $x_i = 0$ para toda $i$. $$S = 0 \oplus 0 \oplus \dots \oplus 0 = 0$$ Así que el estado final es una posición P (al jugador que le toca no tiene movimientos y pierde).

Paso 2: Pasar de una posición N a una posición P Supón que el estado actual tiene una suma-Nim $S \neq 0$. Lo que hay que mostrar es que existe una pila $x_k$ y un nuevo tamaño $x_k' < x_k$ que hace que la nueva suma-Nim sea 0. Toma $d$ como la posición del bit más significativo (MSB) de $S$. Como $S$ tiene un 1 en la posición $d$, al menos una pila $x_k$ debe tener también un 1 en esa misma posición (si no, la suma XOR ahí sería 0). Elige una pila $x_k$ con esa característica y define el nuevo tamaño: $$x_k' = x_k \oplus S$$ Ahora checa estas dos cosas:

1. El movimiento es legal ($x_k' < x_k$): Como $x_k$ y $S$ tienen un 1 en la posición $d$, al hacer $x_k \oplus S$ ese bit cambia de 1 a 0. Aunque los bits más chicos cambien, el bit más significativo es el que manda. Por eso, quitar el bit en $d$ garantiza que $x_k' < x_k$.
2. El nuevo estado es una posición P: La nueva suma-Nim $S_{new}$ queda así: $$S_{new} = x_1 \oplus \dots \oplus x_k' \oplus \dots \oplus x_n$$ Si sustituyes $x_k' = x_k \oplus S$: $$S_{new} = x_1 \oplus \dots \oplus (x_k \oplus S) \oplus \dots \oplus x_n$$ Si reordenas los términos (por asociatividad y conmutatividad): $$S_{new} = (x_1 \oplus \dots \oplus x_k \oplus \dots \oplus x_n) \oplus S$$ $$S_{new} = S \oplus S = 0$$

Paso 3: Pasar de una posición P a una posición N Supón que el estado actual tiene una suma-Nim $S = 0$. Tienes que elegir una pila $x_k$ y cambiarla a $x_k'$ con $x_k' < x_k$. La nueva suma-Nim $S_{new}$ es: $$S_{new} = x_1 \oplus \dots \oplus x_k' \oplus \dots \oplus x_n$$ Sabes que la suma original era $0 = x_1 \oplus \dots \oplus x_k \oplus \dots \oplus x_n$. Entonces, $S_{new}$ es la suma original pero cambiando $x_k$ por $x_k'$. $$S_{new} = 0 \oplus x_k \oplus x_k' = x_k \oplus x_k'$$ Como el movimiento tiene que cambiar el tamaño de la pila, $x_k \neq x_k'$. Por lo tanto, $x_k \oplus x_k' \neq 0$. Así que cualquier movimiento desde un estado con suma-Nim 0 te lleva a un estado con suma-Nim distinta de 0.

Conclusión: Como el juego es finito (los tamaños de las pilas siempre bajan), tiene que terminar. Si empiezas en una posición N, siempre puedes obligar al otro a caer en una posición P. Tu oponente no tendrá de otra más que devolverte el juego en una posición N. Al final, tu oponente se verá obligado a moverse desde una posición P al estado terminal (que es una posición P para el que le toca, o sea que tú te llevaste el último objeto). ¡Por eso la estrategia funciona! $\square$