XOR como suma binaria sin acarreo.
El juego de Nim es el juego imparcial fundamental en la teoría de juegos combinatorios. Consiste en varias pilas de fichas, donde dos jugadores se turnan para quitar cualquier cantidad de fichas de una sola pila. El juego termina cuando ya no quedan fichas y, bajo la convención de juego normal, el último jugador en mover gana. El análisis de Nim depende totalmente de la representación binaria de los tamaños de las pilas. La herramienta central es la Suma-Nim, que es el OR exclusivo (XOR) bit a bit de los tamaños de las pilas. En términos aritméticos, esto equivale a la suma binaria sin acarreo.
Esta técnica es crucial porque reduce un espacio de estados que podría ser muy complejo a un solo valor numérico. Según el Teorema de Bouton, una posición es perdedora (una posición $\mathcal{P}$) si y solo si la Suma-Nim de los tamaños de las pilas es cero. Por el contrario, una posición es ganadora (una posición $\mathcal{N}$) si la Suma-Nim es distinta de cero. Este análisis binario te permite determinar al ganador de cualquier estado al instante y te da un algoritmo constructivo para encontrar el movimiento ganador: cambiar el tamaño de una pila para forzar que la nueva Suma-Nim sea cero.
La intuición detrás de usar la representación binaria está en la independencia de los dígitos binarios durante la operación XOR. Como no hay acarreo, puedes ver el juego como varios sub-juegos independientes que se