El juego de Nim, del que existen varias variantes, es el más conocido de los juegos de estrategia pura para dos jugadores, que juegan por turnos y en el que pierde quien ya no puede jugar. Sus orígenes son probablemente muy antiguos. Fue popularizado en 1961 por la película de Alain Resnais y Alain Robbe-Grillet, El año pasado en Marienbad.
¡El juego de las cerillas de Marienbad, resuelto! -------------------------------------------
El principio es el siguiente: se disponen las cerillas en varias filas, cada una con cierto número de cerillas. En cada turno, el jugador elige una fila y toma de ella tantas cerillas como quiera —al menos una—. Gana el último que puede jugar.
Como hemos visto en los artículos anteriores de este dosier, en este tipo de juegos cada posición (o estado) es ganadora o perdedora para el jugador al que le toca jugar. Conocerlo para cada estado permite que ambos jugadores apliquen una estrategia óptima.
Comencemos por presentar un método de cálculo de esta naturaleza en el juego de Marienbad. Su resolución, a la vez sencilla y espectacular, recurre a la descomposición binaria y a la suma sin acarreo, ideada en 1901 por el matemático estadounidense Charles Leonard Bouton (1869‒1922).