The Game of Nim

How to Play Nim

The game of nim starts with a group of nim heaps, each of which contains one or more objects, traditionally matchsticks.

Each player takes turns removing one or more objects from a single nim heap. It is OK to remove and entire heap.

The player who picks up the last of the objects wins the game.

Suggested Configurations and Variations

One good configuration consists of three nim heaps, with three, five, and seven objects, respectively, with each player picking any number of objects (one or more), from any one heap during each turn.
Try heaps with other combinations of numbers.
For a variation from the standard rules, try one nim heap of 22 objects, with each player allowed to pick up 1, 2, 3, or 4 objects on each turn.

How to Win at Nim

One Heap

In a game of nim where you have one nim heap, and you are allowed to remove from 1 to 4 objects at a time, you can win if you leave the heap with a multiple of 5 objects after your turn. Thereafter, no matter what your opponent does, you can always restore the number of objects to a multiple of 5 when you take your turn. If you cannot leave the heap with a multiple of 5 objects, then your opponent has the advantage, and only an error by your opponent can put you in a position to win the game.

More Than One Heap

In a game of nim that involves nim heaps where you can take as many objects as you want from any one of the heaps during your turn, you need to be able to compute a nim sum, that characterizes the configuration of the game. Here's how to do it:

Express the number of objects in each nim heap as a binary number, with the only digits being 0 and 1.
Fill out the smaller binary numbers with '0's on the left, if necessary, so that all the numbers have the same number of digits.
Sum the binary numbers, but do not carry
Replace each digit in the sum with the remainder that results when the digit is divided by 2.
This yields the nim sum.
To win at nim, always make a move, when possible, that leaves a configuration with a nim sum of 0. If you cannot do this, your opponent has the advantage, and you have to depend on his or her committing an error in order to win.
- Note that if the configuration you are given has a nim sum not equal to 0, there always is a move that creates a new configuration with a nim sum of 0. However, there are usually also moves that will yield configurations that give nim sums not equal to 0, and you need to avoid making these.
- Also note that if you are given a configuration that has a nim sum of 0, there is no move that will create a configuration that also has a nim sum of 0.

Example of Computing a Nim Sum

Let's say you have three nim heaps, with 3, 7, and 11 matchsticks, respectively.

As binary numbers, these quantities are 11, 111, and 1011, respectively.
Filling out with '0's yields 0011, 0111, and 1011.
Summing with carrying, we get:
```
 0011
+0111
+1011
 ----
 1133
```
Taking the remainders after dividing each digit by 2 yields 1111, which is not equal to 0. Therefore, this configuration is a winning position for the person who is about to take a turn. It follows that you should try not to create this configuration when you take your turn. Now, you need to plan a move that creates a configuration with a nim sum of 0. How about removing 7 matchsticks from the pile that now has 11, leaving 4? We then have:
```
 0011
+0111
+0100
 ----
 0222
```
Taking the remainders after dividing by 2 gives us 0000. This is a configuration that we want to leave for our opponent.
Try the Nim Sum Calculator Applet. You will need to have a Java 2 plug-in to do this.

A Practice Problem

You are given a configuration with 3 nim heaps that have 3, 7, and 11 matchsticks respectively. What is the nim sum? If it is not 0, what can you do to make it 0?

Another Practice Problem

Consider the configuration shown to the right. There are 2 nim heaps composed of matchsticks that form each of the letters N, I, and M, for a total of 6 nim heaps all together.

Using the standard rules that allow a player to pick up 1 or more matchsticks from any one heap during each turn, which player has the advantage, the first or the second one? What is the nim sum of this configuration? How can the player who has the advantage at the beginning of this game maintain it without going through the trouble of computing nim sums?