Some games are all about luck. Your winning chance depends on the roll of a die or the cards you've been dealt. But there are other games that are only about strategy: if you play cleverly, you're guaranteed to win.

A great example of this is the ancient game of Nim. Whatever the state of the game, there is a winning strategy for one of the two players. And a very cute form of addition tells you which of the two players it is.

The rules of Nim

The traditional game of Nim is played with a number of coins arranged in heaps: the number of coins and heaps is up to you. There are two players. When it's a player's move he or she can take any number of coins from a single heap. They have to take at least one coin, though, and they can't take coins from more than one heap. The winner is the player who makes the last move, so there are no coins left after that move. (Some people play the game the other way around, with the last person to make a move losing the game, but we'll ignore that version for the moment.)

It's clear that there is no luck involved here. You can work out the best move to make by cleverly predicting the sequence of moves that would follow it.

As an example of how the game works, suppose there are three heaps with three, four and five coins respectively. Here is how the game could develop:

The question we're interested in is this: given a particular configuration of heaps and coins, is there a winning strategy for one of the players? That is; is one of the players guaranteed to win if he or she plays the right moves?

Let's start by playing with some examples. Suppose the two players are called A and B, and suppose that A goes first. Suppose there are two heaps with a coin each. Then clearly, player B is guaranteed to win: A has to take one of the two coins, leaving B to take the last one.

Now suppose that there are two heaps, one of which contains two coins and the other one. Now player A has a winning strategy: take one of the coins in the two-coin heap. This leaves two heaps with a coin each and B to go next. And as we saw in the previous example, this means that A will win.

Let's do one more: suppose that there are two heaps with two coins each. Now player B has a winning strategy. If A takes an entire heap, then B should take the remaining heap and win. If A takes only one coin of one of the heaps, then we are in the same situation as in the previous example, with B to go first. Therefore, B is guaranteed to win if she takes one coin from the two-coin heap.

From this series of examples you can't help but feel that there is some sort of pattern here: that there should be some sort of clever trick that tells you for a given arrangement of coins and heaps whether there is a winning strategy for one of the players. The American mathematician Charles Bouton (1869-1922) felt the same and set himself the daunting task of analysing the game completely. In 1902 he found the trick — and it's subtle! To figure out whether there is a winning strategy and for which player, you first need to...

Go binary

The secret is to write the sizes of the heaps as binary numbers (if you already know how to do this, skip this part.) To see how to do this, let's first remind ourselves of how the ordinary decimal way of writing numbers works. Let's take the number 4302 as an example. The digit 4 in this number doesn't stand for the number 4, rather it stands for 4000, or 4 x 1000. Similarly, 3 doesn't stand for 3 but for 300 = 3 x 100, 0 stands for 0 x 10, and 2 stands for 2 x 1. So 4302 means

4 x 1000 + 3 x 100 + 0 x 10 + 2 x 1.

Similarly, 7396 stands for

7 x 1000 + 3 x 100 + 9 x 10 + 6 x 1.

What do the numbers 1000, 100, 10 and 1, which appear in these expressions, have in common? They are all powers of 10:

1000 = 10³
100 = 10²
10 = 10¹
1 = 10⁰.

To write a number in decimal notation, you first write it as a sum of consecutive powers of 10 (with the largest power on the left) and then pull out the coefficients of these powers. We can do the same with powers of 2 rather than 10. For example, the binary number 110 stands for

1 x 2² + 1 x 2¹ + 0 x 2⁰ = 4 + 2 +0 = 6 (written in decimal).

And the binary number 10001 stands for

1 x 2⁴ + 0 x 2³ + 0 x 2² + 0 x 2¹ + 1 x 2⁰ = 16 + 0 + 0 + 0 + 1 = 17 (written in decimal).

You can convince yourself that a binary number only consists of the digits 0 or 1: when you write a number as a sum of consecutive powers of 2, no other coefficients are necessary.

Adding the Nim way

The secret to finding the winning strategy hinges on writing the sizes of the heaps (the number of coins in each heap) in binary, and then adding those numbers up — but not using the ordinary way of adding numbers, but something appropriately called Nim addition.

To add some given binary numbers using Nim addition, you first write them underneath each other, as you might for ordinary addition. Then you look at each of the columns in turn. If the number of 1s in a column is odd, you write a 1 underneath it; if it's even, you write a 0 underneath it. Doing this for each column gives a new binary number, and that's the result of the Nim addition.

As an example, let's Nim-add the binary numbers 10, 11, and 100 (which stand for the decimal numbers 2, 3 and 4):

		1	0
		1	1
	1	0	0
	1	0	1

So the result, which is called the Nim sum, is the binary number 101. Nim addition is not the same as ordinary addition: the binary number 101 is 5 in decimal, which is not equal to the ordinary sum 2+3+4 = 9.

Who wins?

When Charles Bouton analysed the game of Nim, he figured out two facts which hold the key to the winning strategy.

Fact 1: Suppose it's your turn and the Nim sum of the number of coins in the heaps is equal to 0. Then whatever you do, the Nim sum of the number of coins after your move will not be equal to 0.

Fact 2: Suppose it's your turn and the Nim sum of the number of coins in the heap is not equal to 0. Then there is a move which ensures that the Nim sum of the number of coins in the heaps after your move is equal to 0.

It is not too difficult to prove that these to facts are always true (see for example this article) but you can also convince yourself by playing around with heaps of coins.

Now suppose you are player A, so you go first. Also suppose that the Nim sum of the number of coins in the heaps is not equal to 0. Your strategy will be this: if possible always make a move that reduces the next Nim sum, the Nim sum after your move, to 0. This would then mean that whatever player B does next, by fact 1 the move would turn the next Nim sum into a number that's not 0.

Let's have a go, keeping track of the Nim sums in a table:

Player to move next	Nim sum	Can this be reduced to 0?	Next Nim sum
A	not 0	Yes	0
B	0	No	not 0
A	not 0	Yes	0
B	0	No	not 0
A	not 0	Yes	0
...	...	...	...

This ping-pong between zero and non-zero Nim sums means that you are guaranteed a win! If player B were to win, she would have to make a move that leaves over no coins at all. That is; she would have to make a move that results in a zero Nim sum which, as we can see, is impossible. Your moves, on the other hand, always reduce the Nim sum to zero. And at some point in the game, the zero Nim sum will correspond to there actually being zero coins left — you've won.

This shows that if the Nim sum of coins in the heaps at the start of the game is not 0, then player A has a winning strategy. The strategy is to always make a move that reduces the next Nim sum to 0. (You can check that this is the strategy played by player A in the example at the beginning of this article.)

If the Nim sum of coins in the heaps at the start of the game is equal to 0, then player B has a winning strategy. Whatever player A does on the first move will result in a non-zero Nim sum when it's B's turn. And by the same reasoning as above, this means that the winning strategy is now in B's hands.

Nim addition rules the world

Nim addition is clearly very useful when you're playing Nim, but that's about it, right? Wrong! It turns out that much of our everyday life depends on this curious way of adding up numbers.

Computers are binary machines. All the information they store, including numbers, is translated in to strings of 0s and 1s. But computers not only store information, they also perform logical operations, based on yes/no answers. For example, given a user name and a password, they need to ask the questions "is the user name correct?" and "is the password correct?" and depending on the answers decide whether or not to let the person entering them log in. Note that this operation takes two inputs (user name correct? password correct?) and returns one output (login yes or login no).

Writing 0 for "no" and 1 for "yes", these logical operations can also be turned into operations involving 0s and 1s. Luckily, it turns out that any logical operation you might ever want to perform can be made out of six basic ones. You simply have to compose them in the correct way.

One of these basic operations is called XOR. It also takes two inputs, each of which can be a 0 or a 1, and returns one output, which can also be a 0 or a 1. Here is the table of outputs XOR returns for a given combination of inputs:

XOR
Input		Output
1	1	0
1	0	1
0	1	1
0	0	0

A closer look at this shows that XOR is exactly the same as Nim addition of the digits 0 and 1:

Nim addition
Input		Output
1	1	1+1 = 0
1	0	1+0=1
0	1	0+1=1
0	0	0+0=0

So, many of the operations your computer performs every day are based on Nim addition — without it, things would be very different. You can find out more in the Plus article A bright idea.

---

About the author

Marianne Freiberger is Editor of Plus.

About this article

This article was inspired by content on our sister site Wild Maths, which encourages students to explore maths beyond the classroom and designed to nurture mathematical creativity. The site is aimed at 7 to 16 year-olds, but open to all. It provides games, investigations, stories and spaces to explore, where discoveries are to be made. Some have starting points, some a big question and others offer you a free space to investigate.