Beating Nim

How to play Nim perfectly, an introduction to proofs in combinatorial games.

Published

20 January 2025

The Game

Last semester I took a small course in proofwriting on some more intermediate topics, one of the proofs I was introduced to was about a turn based game called Nim. And it worked a little something like this:

There are \( n \) rows/categories/sections, here in each row there are \( a_1, a_2, a_3, \ldots, a_n \) items (Could be stones, matchsticks, pencils, or whatever you like). Two players take turns removing items from the rows, and the player who removes the last item wins. An example game may look something like:

Figure. 1 Example game of Nim with three rows of items with 9, 5, and 7 items respectively. Player 2 removes the last item and wins the game.

In this example, player 2 wins. However, by design of the game, there is a strategy for the first player that, if played right, will guarantee a win for the first player always. What I am looking to do is go through this strategy and prove mathematically why this will guarantee a win.

The Strategy

When playing as the first player, the concept to keep in mind to win is the Nim sum. Each row has a number of items, and a binary representation of this number that is used to calculate this sum, by using the logical XOR operator (\( \oplus{} \)) with each binary representation of the number of items in each row. Using the example in Figure. 2. The optimal game of Nim will look something like:

Figure. 2 Example game of Nim with starting configuration from Figure 1. In this case Player 1 removes the last item and wins the game, keeping the Nim sum at zero on his turns.

As we will prove later, so long as Player 1 plays the game optimally, this Nim sum will remain nonzero at the end of Player 2's turns no matter what move is made. And this is what allows for Player 1 to win the game every time. No matter what.

This is pretty interesting on its own. But outside of being a party trick, how exactly can one make sure that the Nim sum is 0 at the end of their turn? And why does this even work in the first place?

To answer the first question, binary counting and operations are very unintuitive for humans to do quickly. So we will need to develop another method to keep track of our Nim sum. To do this, the first constraint we will need to put on ourselves is keeping track of how many groups of \( \{2, 4, 8, 16, ... ,2^{n}\} \) items are present in each row, considering only the largest group \(2^{n}\) one can make for each row. For Player 1 to maintain their advantage, they need an even number of groups present for each configuration of row.

Figure. 3 Example game of Nim with starting configuration from Figure 1. Notice that we need to make sure that we have an even number of groups of 8.

In the case of Figure 3 above, we will need to remove an item from the first row, given this rule alone we will need to remove at least five items so that we do not have an odd number of groups of eight, or four. But we must be careful, we can't just remove an arbitrary amount of items greater than four. We need to make sure that we are also treating the remainders, or lower powers of 2 properly as well. In this case, there are a few ways to think about or remembering how to do this. The best way is to try breaking these remainders further into groups, and just referring back to our inital rule and trying to balance this number so all groups are even, this works especially well for larger numbers of items.

Figure. 4 Algorithm of breaking down remainders into groups of powers of 2. Checking residuals recursively until an uneven number of groups is found.

Doing this recursive check after each term will guarantee that the Nim sum is zero at the end of Player 1's turn. And this is the strategy that will allow for Player 1 to win every time. A short explanation of this comes about from the definition of the XOR operator. Since it works bitwise, and there are 3 numbers representing the number of items in binary, we only need to concern ourselves with 8 possible operations:

\[ 1 \oplus 1 \oplus 1 = 1 \\ \] \[ 1 \oplus 0 \oplus 0 = 1 \\ \] \[ 0 \oplus 1 \oplus 0 = 1 \\ \] \[ 0 \oplus 0 \oplus 1 = 1 \\ \] \[ 1 \oplus 1 \oplus 0 = 0 \\ \] \[ 1 \oplus 0 \oplus 1 = 0 \\ \] \[ 0 \oplus 1 \oplus 1 = 0 \\ \] \[ 0 \oplus 0 \oplus 0 = 0 \\ \]

Note how the result of the operation is only zero when there are an even number of ones involved in the operation. This is exactly why we need to make sure that we have an even number of groups of each power of 2 in each row. As it maintains the condition that the XOR operator will output zero for each sum for all items and their binary representation. We will see that this condition will hold for games of all possible rows and item numbers.

The Proof

To prove the winning strategy rigorously, we characterize game positions using the Sprague-Grundy theorem for impartial games. We define two types of positions:

  • P-positions (Previous player wins): Positions where the player who just moved has the advantage. The player to move will lose with optimal play.
  • N-positions (Next player wins): Positions where the player about to move has the advantage. The player to move will win with optimal play.

Definition: For a game state with piles of sizes \(a_1, a_2, \ldots, a_n\), the Nim sum is defined as: \[ S = a_1 \oplus a_2 \oplus \cdots \oplus a_n \] where \(\oplus\) denotes the bitwise XOR operation.

Theorem: A position in Nim is a P-position if and only if its Nim sum equals zero.

Proof: We establish this by showing three properties that uniquely characterize P-positions and N-positions:

Property 1: The terminal position is a P-position.

The terminal position has all piles empty: \(a_1 = a_2 = \cdots = a_n = 0\). The Nim sum is: \[ S = 0 \oplus 0 \oplus \cdots \oplus 0 = 0 \] The player to move cannot make any move and loses. Thus, the terminal position is a P-position with Nim sum zero.

Property 2: From any position with nonzero Nim sum (N-position), there exists at least one move to a position with zero Nim sum (P-position).

Let \(S = a_1 \oplus a_2 \oplus \cdots \oplus a_n \neq 0\). Let \(d\) be the position of the most significant bit (leftmost 1) in \(S\).

Since \(S \neq 0\), there must be an odd number of piles with a 1 in bit position \(d\). Therefore, at least one pile \(a_k\) has a 1 in bit position \(d\).

Consider the value \(a_k' = a_k \oplus S\). We claim that \(a_k' < a_k\):

  • Both \(a_k\) and \(S\) have a 1 in bit position \(d\).
  • Therefore, \(a_k \oplus S\) has a 0 in bit position \(d\).
  • All bits more significant than \(d\) in \(S\) are 0 (by definition of \(d\)).
  • Thus, \(a_k' = a_k \oplus S < a_k\) since the most significant differing bit is position \(d\), where \(a_k\) has 1 and \(a_k'\) has 0.

Since \(a_k' < a_k\), reducing pile \(a_k\) to \(a_k'\) is a valid move. The new Nim sum after this move is: \[ S' = a_1 \oplus \cdots \oplus a_k' \oplus \cdots \oplus a_n = a_1 \oplus \cdots \oplus (a_k \oplus S) \oplus \cdots \oplus a_n \] By associativity and commutativity of XOR: \[ S' = (a_1 \oplus \cdots \oplus a_k \oplus \cdots \oplus a_n) \oplus S = S \oplus S = 0 \] Thus, from any N-position, we can move to a P-position.

Property 3: From any position with zero Nim sum (P-position), every possible move leads to a position with nonzero Nim sum (N-position).

Let \(S = a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0\). Suppose we reduce pile \(a_k\) to some value \(a_k'\) where \(a_k' < a_k\) (i.e., \(a_k' \neq a_k\)).

The new Nim sum is: \[ S' = a_1 \oplus \cdots \oplus a_k' \oplus \cdots \oplus a_n \] We can rewrite this using the fact that \(a_k = a_k \oplus 0 = a_k \oplus S\) (since \(S = 0\)): \[ S' = S \oplus a_k \oplus a_k' = 0 \oplus a_k \oplus a_k' = a_k \oplus a_k' \] Since \(a_k' \neq a_k\), we have \(a_k \oplus a_k' \neq 0\), so \(S' \neq 0\).

Thus, every move from a P-position leads to an N-position.

Conclusion: Properties 1-3 establish that positions with Nim sum zero are exactly the P-positions:

  • The game always terminates (piles decrease).
  • The terminal state has Nim sum 0 (P-position).
  • From Nim sum \(\neq 0\), one can always reach Nim sum \(= 0\).
  • From Nim sum \(= 0\), one must reach Nim sum \(\neq 0\).

Therefore, if the initial Nim sum is nonzero, the first player can always win by moving to a position with Nim sum zero, forcing the opponent into an N-to-P disadvantage on every turn.

∎

Corollary: If the initial Nim sum is zero, the second player has a winning strategy.

This follows directly from the theorem: if the game starts in a P-position (Nim sum = 0), the first player must move to an N-position, giving the second player the winning advantage.

Play Nim

Try playing an interactive game of Nim below! The AI will play optimally against you.

Select a row and the number of items to remove:



  1. Charles L. Bouton. (1901). Nim, A Game with a Complete Mathematical Theory. Annals of Mathematics, 3(1/4), 35-39. https://doi.org/10.2307/1967631