El juego clásico con estrategia basada en XOR.
Nim es el juego imparcial fundamental que juegas con distintos montones de objetos (que suelen ser monedas, piedras o cerillos). En la versión estándar (Juego Normal), tú y tu oponente toman turnos para quitar cualquier cantidad positiva de objetos de un solo montón. Gana quien haga el último movimiento, dejando al oponente sin jugadas. Aunque el juego parece simple, el número de estados posibles crece muchísimo con el tamaño de los montones, lo que hace que un análisis de fuerza bruta sea imposible para valores grandes.
El juego es clave en la teoría de juegos combinatorios por el Teorema de Sprague-Grundy, que dice que todo juego imparcial bajo la convención de juego normal es equivalente a un solo montón de Nim de un tamaño específico. Por eso, si entiendes Nim, ya tienes la solución para una clase enorme de juegos matemáticos. La estrategia depende totalmente de la representación binaria de los tamaños de los montones; específicamente, usas la operación XOR (OR exclusivo), que también es la suma sin acarreo en base 2.
La idea clave es la distinción entre posiciones ganadoras (posiciones N) y posiciones perdedoras (posiciones P). Una posición es perdedora si la "suma Nim" de los tamaños de los montones es cero; de lo contrario, es una posición ganadora. Si estás en una posición ganadora, la estrategia óptima es hacer un movimiento que cambie la suma Nim a cero, forzando a tu oponente a un estado perdedor. Como el juego tiene que terminar (es finito y no tiene ciclos), esta estrategia te garantiza la victoria si la posición inicial tiene una suma Nim distinta de cero.