The game of Nim, which comes in several variants, is the best known two-player game of pure strategy in which each player moves alternately, and the loser is the one who can no longer move. Its origins are probably very ancient. It was popularized in 1961 by Alain Resnais and Alain Robbe-Grillet's film, L’Année dernière à Marienbad (Last Year at Marienbad).
The Marienbad matchstick game solved!
-------------------------------------------
The idea: matchsticks are arranged in several rows, each containing a certain number of matchsticks. On each turn, the player chooses a row and takes, from that row, as many matchsticks as they want (at least one). The last player able to move wins.
As seen in the previous articles in this series, in this type of game, every position (or state) is inherently winning or losing for whoever inherits it. Knowing this for every state allows each player to apply an optimal strategy.
Let's begin by describing a method for computing this in the Marienbad game. Its solution, both simple and spectacular, relies on binary decomposition and carry-free addition, devised in 1901 by the American mathematician Charles Leonard Bouton (1869–1922).
