Calcular el XOR de los tamaños de las pilas.
La suma-Nim es la herramienta fundamental que usas para analizar juegos imparciales, específicamente el juego de Nim. La definimos como la suma OR exclusiva bit a bit (XOR) de los tamaños de los montones, y a menudo la escribimos con el símbolo $\oplus$. A diferencia de la suma normal, la suma-Nim suma sin llevar el acarreo: si sumas dos dígitos binarios, $1+1$ se vuelve $0$ en lugar de $10_2$. En el contexto de Teoría de Juegos, el teorema de Sprague-Grundy generaliza este concepto y dice que todo juego imparcial bajo la convención de juego normal es equivalente a un montón de Nim de cierto tamaño, conocido como su valor de Grundy o nim-valor.
Esta técnica es crucial porque da una solución completa al juego de Nim, como lo estableció Charles Bouton en 1901. Clasificamos el estado del juego basándonos en la suma-Nim de los tamaños de los montones. Un estado es una posición perdedora (una posición $\mathcal{P}$, donde el jugador anterior tiene la estrategia ganadora) si y solo si la suma-Nim es cero. Por el contrario, un estado es una posición ganadora (una posición $\mathcal{N}$, donde el siguiente jugador tiene la estrategia ganadora) si la suma-Nim es distinta de cero. Esta distinción binaria te permite determinar quién gana en un juego complejo al instante, sin tener que mapear todo el árbol del juego.
La intuición de usar la representación binaria y el XOR está en el objetivo del juego: forzar al oponente a un estado del que no pueda recuperarse. Si ves los tamaños de los montones como números binarios, un movimiento consiste en cambiar los bits de un montón específico. La operación XOR te permite controlar la paridad de los bits en cada columna. Una estrategia ganadora consiste en hacer un movimiento que "equilibre" todas las columnas binarias (haciendo que el conteo total de 1s en cada columna sea par), lo que resulta en una suma-Nim de cero. Una vez que la suma es cero, cualquier movimiento del oponente necesariamente va a desequilibrar al menos una columna, permitiendo que el jugador ganador la vuelva a equilibrar en el siguiente turno.
Definición de la Suma-Nim Para un juego de Nim con montones de tamaños $x_1, x_2, \dots, x_n$, la suma-Nim $S$ la definimos como: $$ S = x_1 \oplus x_2 \oplus \dots \oplus x_n $$ donde $\oplus$ denota la operación XOR bit a bit. Si la representación binaria de $a$ es $\sum a_i 2^i$ y la de $b$ es $\sum b_i 2^i$, entonces $a \oplus b = \sum ((a_i + b_i) \pmod 2) 2^i$.
Teorema de Bouton Sea $S$ la suma-Nim de los tamaños actuales de los montones.
Construcción del Movimiento Óptimo Si la suma-Nim actual es $S \neq 0$, un movimiento ganador consiste en elegir un montón $x_k$ y reducirlo a un tamaño $x_k'$, de tal manera que la nueva suma-Nim sea $0$. Calculas el tamaño objetivo como: $$ x_k' = x_k \oplus S $$ Este movimiento es válido si y solo si $x_k' < x_k$. Un montón $x_k$ así siempre existe; específicamente, cualquier montón $x_k$ que tenga un $1$ en la posición del bit más significativo (MSB) de $S$ es un candidato válido.
Teorema: Una posición en Nim con tamaños de montones $(x_1, x_2, \dots, x_n)$ es una posición perdedora (posición $\mathcal{P}$) si y solo si la suma-Nim $S = x_1 \oplus x_2 \oplus \dots \oplus x_n = 0$.
Demostración: Para probar esto, hay que demostrar tres propiedades sobre la suma-Nim $S$:
Paso 1: La posición terminal El juego termina cuando todos los montones están vacíos, es decir, $x_i = 0$ para todo $i$. $$ S = 0 \oplus 0 \oplus \dots \oplus 0 = 0 $$ Así, el estado terminal tiene una suma-Nim de 0. Esta es una posición $\mathcal{P}$ por definición.
Paso 2: Moverse desde $S=0$ Supón que el estado actual tiene una suma-Nim $S = 0$. Un movimiento consiste en cambiar el tamaño de un solo montón $x_k$ a un tamaño menor $x_k'$ (donde $x_k' < x_k$). Sea $S'$ la nueva suma-Nim. Por las propiedades del XOR (específicamente que $A \oplus A = 0$), puedes escribir: $$ S' = x_1 \oplus \dots \oplus x_k' \oplus \dots \oplus x_n $$ $$ S' = S \oplus x_k \oplus x_k' $$ Como $S=0$, esto se simplifica a: $$ S' = 0 \oplus x_k \oplus x_k' = x_k \oplus x_k' $$ Como $x_k' \neq x_k$, su suma XOR no puede ser cero. Por lo tanto, $S' \neq 0$. Cualquier movimiento desde una suma-Nim de cero lleva a una suma-Nim distinta de cero.
Paso 3: Moverse desde $S \neq 0$ Supón que la suma-Nim actual es $S \neq 0$. Hay que mostrar que existe un montón $x_k$ y un nuevo tamaño $x_k' < x_k$ tal que la nueva suma-Nim $S' = 0$. Sea $d$ la posición del bit más significativo (MSB) de $S$. Como $S \neq 0$, ese bit existe. Como el bit $d$-ésimo de $S$ es 1, debe haber un número impar de montones con un 1 en el bit $d$-ésimo. Por lo tanto, hay al menos un montón $x_k$ tal que el bit $d$-ésimo de $x_k$ es 1.
La idea es hacer este movimiento: cambia $x_k$ por $x_k' = x_k \oplus S$. Primero, verifica que esto resulta en una nueva suma-Nim de 0: $$ S' = S \oplus x_k \oplus x_k' = S \oplus x_k \oplus (x_k \oplus S) = (S \oplus S) \oplus (x_k \oplus x_k) = 0 $$ Luego, verifica que este es un movimiento legal (es decir, $x_k' < x_k$). Considera las representaciones binarias. El MSB de $S$ está en la posición $d$. $$ x_k' = x_k \oplus S $$ En la posición del bit $d$, $x_k$ tiene un 1 y $S$ tiene un 1, así que $x_k \oplus S$ tiene un 0. Para todas las posiciones de bit mayores que $d$, $S$ tiene ceros, así que los bits de $x_k$ se quedan igual en $x_k'$. Como la diferencia más significativa entre $x_k$ y $x_k'$ ocurre en el bit $d$, donde $x_k$ es 1 y $x_k'$ es 0, se sigue que $x_k' < x_k$.
Conclusión Como siempre puedes forzar el juego desde un estado con $S \neq 0$ a un estado con $S=0$, y cualquier movimiento desde $S=0$ resulta en $S \neq 0$, el jugador que empieza desde una suma-Nim distinta de cero puede asegurar que eventualmente llegará al estado terminal (puros ceros) en su turno. Por lo tanto, $S=0$ caracteriza las posiciones perdedoras. $\square$