Nim

Definition Nim is a game for two players with a finite number of piles of counters. The players take turns. On each turn a player chooses one pile that is not empty and removes any positive number of counters from it, from one counter up to the whole pile. No other pile changes, and no pile ever grows. Both players see all the piles, and nothing is decided by chance. Under normal play, the rule used on this page, the player who takes the last counter wins, so a player who faces only empty piles has lost.

The game is solved by Bouton’s theorem, stated in its own card below. Write $a_1, \dots, a_k$ for the pile sizes and $S = a_1 \oplus \cdots \oplus a_k$ for their nim-sum. The player to move can force a win exactly when $S \ne 0$, and the winning moves are exactly the moves that leave a nim-sum of $0$. Under the misère rule, in which taking the last counter loses, this strategy needs a change near the end of the game.

Definition Every whole number $n \ge 1$ can be written in exactly one way as a sum of different powers of two, taken from $1, 2, 4, 8, 16, \dots$, and the number $0$ is the sum of no powers at all. Its binary form records this sum with one digit for each power, $1$ if the power is used and $0$ if it is not, with the largest power on the left. A subscript $2$ marks a binary form, so $101_2$ means $4 + 1 = 5$. Zeros on the left change nothing, so several numbers can be written with the same number of digits and lined up in columns, one column for each power. Two different numbers can be compared in binary by reading from the left. If $a > b$, then at the first place from the left where their binary forms differ, $a$ has the digit $1$ and $b$ has the digit $0$.

Definition The nim-sum of whole numbers $a_1, \dots, a_k$, written $a_1 \oplus \cdots \oplus a_k$, is found by writing the numbers in binary, lined up in columns, and counting the digits $1$ in each column. The nim-sum has the digit $1$ in each column where the count is odd and $0$ in each column where it is even. The same operation is called bitwise exclusive or, or XOR. It is not ordinary addition, because nothing is carried from one column to the next. For all whole numbers $a$, $b$ and $c$ it satisfies

So the order of the numbers does not matter, and a number that appears twice cancels. In particular $a \oplus b = 0$ exactly when $a = b$.

Definition Bouton’s theorem says that in Nim under normal play, the position with piles $a_1, \dots, a_k$ is a losing position for the player to move exactly when

Every other position is winning, and a winning move is found as follows. Let $S \ne 0$ be the nim-sum, find the leftmost digit $1$ of $S$ in binary, choose a pile $a$ that also has a $1$ in that place, and reduce that pile to $a \oplus S$ counters. Such a pile exists, because that column holds an odd number of ones. The new size is smaller than $a$, because $a \oplus S$ agrees with $a$ to the left of that place and has $0$ where $a$ has $1$, so the move is legal. The winning moves are exactly the moves of this kind.

The proof has three steps. First, a move from nim-sum $0$ changes one pile from $a$ to a different number $b$. Some column of $a$ and $b$ differs, the count of ones in that column changes by one, and so the new nim-sum $a \oplus b$ is not $0$. Second, from nim-sum $S \ne 0$, changing a pile from $a$ to $b = a \oplus S$ gives the new nim-sum

because nim-summing $a$ again cancels the old pile and $b$ brings in the new one. Third, each move removes at least one counter, so the game ends after finitely many moves, at the empty position, whose nim-sum is $0$. Suppose a player leaves nim-sum $0$. By the first step the opponent cannot leave nim-sum $0$, so in particular cannot empty the board, and by the second step the player can leave nim-sum $0$ again. Repeating this until the game ends, the player who keeps leaving nim-sum $0$ is the one who takes the last counter. The theorem is named after Charles L. Bouton, who published it in the early 1900s.

Definition A combinatorial game, in the sense used here, is a game for two players who move alternately and both know the whole position at every moment, with no dice, shuffled cards or other chance. The rules say which moves are legal from each position, every play ends after finitely many moves, and the game cannot end in a draw, because a rule such as normal play decides the winner. Such a game is impartial when both players have the same moves available from every position, and partisan when the available moves depend on whose turn it is. Backward induction shows that every position of a combinatorial game is either a winning or a losing position for the player to move. Some authors use the term more broadly and include games that can end in a draw, such as tic-tac-toe.