# Nim - Strategy Game or Scam?

A stranger you get talking to in a bar challenges you to a simple game. He takes a small handful of peanuts and sprinkles them into three or four random piles. He invites you to take a number of peanuts from any one of the piles. Then it's his turn to take a number of peanuts from any one of the remaining piles. You carry on taking turns to do this, but the player who takes the last peanut from the last remaining pile loses the game.

Perhaps the loser buys the next round of drinks, or there's a small sum of money riding on the outcome. Perhaps you won the first round and the stranger asks you for another round 'to give him the chance to win his money back'. Beware! If you've not encountered this game before, it's a scam. The stranger can win every time. He may have let you win the first round to get you hooked. Don't fall for the bait, but read on to discover how he does it, and how to turn the tables on him.

### The Game

The rules of Nim are simple. You start with a number of piles containing a discrete number of objects; whether it's peanuts, matchsticks or counters doesn't matter. Having four or more piles, and up to ten items in each pile is typical, but while you're learning how to master the game, start with smaller numbers of each.

It's a two-player game, and players should take turns to start. One player should set up the peanuts, the other takes the first turn, and these roles will alternate in the games that follow.

A typical game, between players Annie and Bob could be as follows:

• Annie sets up three random piles (we'll call them A, B and C), which happen to contain 5, 4 and 6 peanuts respectively.

• Bob takes one peanut from pile B, leaving the number of peanuts in the three piles as follows: [5,3,6]

• Annie takes four peanuts from pile A: [1,3,6]

• Bob takes four peanuts from pile C: [1,3,2]

• Annie takes one peanut from pile C: [1,3,1]

• Bob takes two peanuts from pile B: [1,1,1]

• Annie is doomed! She takes the peanut from pile C: [1,1,0]

• Bob takes the peanut from pile B: [1,0,0], leaving Annie to pick up the last peanut and lose the game.

That was bad luck on Annie, but could she have won? In the circumstances, no. Bob controlled the game from start to finish. So how did he do it?

### How To Win at Nim

Bob used a bit of mental arithmetic, but to learn it you have to understand a little bit of number theory. It's not too difficult, and it's well worth making the effort.

#### Number Bases

We Earthlings work with a decimal number system. We have ten number symbols (0, 1, 2, ... 9), and when we reach ten we write one and zero, indicating one multiplied by ten, plus zero. When we write 42 we mean four multiplied by ten, plus two. 127 means one multiplied by ten squared, plus two multiplied by ten, plus seven. For this decimal system, we say we work in base ten.

But we don't have to work in base ten. When we discover intelligent aliens from the planet Thrarg, having only seven fingers, we will find them working with a base seven number system. 42 items in our system will be written as 60 in theirs: six times seven, plus zero. They will have no symbols for seven (7) , eight (8) and nine (9).

Our mathematics works in any base number system, which is handy, but if you want to understand the game of Nim you have to be able to think in base 2, also known as binary.

#### Step 1 - Teach Yourself Binary

Binary has only the digits 0 and 1. If we want to write the decimal number two in binary, we write 10, i.e. one 2 plus zero. Five in decimal is written as 101 in binary: one 4 (22) plus zero 2s plus one 1.

42 in decimal is written as 101010 in binary: one 32 (25), plus zero 16s (24), plus one 8 (23), plus zero 4s (22), plus one 2, plus zero 1s: 32 + 0 + 8 + 0 + 2 + 0 = 42.

This is your first challenge - you need to be able to think of a number in terms of its binary coefficients, ie which powers of two you need to make up that number. Here's a simple table of binary coefficients for numbers up to ten:

 Decimal Binary Number in Pile Number of 8s Number of 4s Number of 2s Number of 1s 1 0 0 0 1 2 0 0 1 0 3 0 0 1 1 4 0 1 0 0 5 0 1 0 1 6 0 1 1 0 7 0 1 1 1 8 1 0 0 0 9 1 0 0 1 10 1 0 1 0

To be adept at Nim, you need to know this table like the back of your hand, so learn it, and read on when you can instantly say that, for example, seven in binary is 111 - one 4, plus one 2, plus one 1.

#### Step 2 - Counting Coefficients

OK, so we're good at binary, but what do we do with it? The answer is we need to convert each of the piles of peanuts into their binary equivalents, and count the coefficients.

Take the opening situation from Annie and Bob's game: the three piles contained 5, 4 and 6 peanuts respectively. If we convert these into binary, we find that pile A contains one 4 plus one 1, pile B contains one 4, and pile C contains one 4 plus one 2.

We need to add these together: It makes a total of three 4s, one 2 and one 1, as this table shows:

 Pile Number of Peanuts (decimal) 8s 4s 2s 1s A 5 0 1 0 1 B 4 0 1 0 0 C 6 0 1 1 0 Total 0 3 1 1

This is your next challenge, can you visualise a number of piles, convert them into binary, and then remember the total number of each binary coefficient? The Nim expert can, so have a little practice, and then read on when you're confident enough to continue.

#### Step 3 - Balance the Set

This step is the trickiest, but it's the last real piece of mental arithmetic you need, so it's worth the effort - after all, you've come so far!

Right, what you need to do is to remove a number from one of the piles, so that when you work out the totals of binary coefficients, they are all even numbers. So, for example, you could take peanuts to leave piles with two 4s, zero 2s and four 1s1, or you could leave two 2s and two 1s.

Let's look at Bob's first play. He started, you will remember, with piles containing 5, 4 and 6 peanuts. We converted those to binary, and we counted the coefficients, and we found he had three 4s, one 2 and one 1.

In fact, Bob has an odd number of each binary coefficient. He can't add peanuts to make an even number of 4s, so he has to take away one of those coefficients of 4. At the same time, he needs to make his coefficients of 2 and 1 both even - he has one of each.

Bob has two options to consider. If he were to take away a whole pile of seven peanuts, this would take away one 4, one 2 and one 1 from the total of coefficients, leaving him with two 4s, zero 2s and zero 1s. The trouble is, there isn't a pile of seven.

Bob's only other option is to take away a coefficient of 4, but to add a coefficient of 2 and a coefficient of 1. In fact he can do this if he takes away one peanut from a pile of four, leaving a pile of three.

So that's what Bob did - he took away one peanut from a pile of four. He left piles of 5, 3 and 6. In binary, these are 101, 011 and 110. In total there are two coefficients of 4, two 2s and two 1s. It's balanced.

Now it's Annie's turn to play, but try as she might, she can't take away peanuts from one pile in this balanced situation, and leave an even number of coefficients. She has to leave an odd number somewhere, and Bob can rectify that on his next go - he is controlling the game.

#### Step 4 - But Beware!

There's one more thing you need to know about. It's an odd situation which occurs near the end of the game where the above rules don't apply, for some strange reason.

In Annie and Bob's game earlier, you may have seen Bob was faced with the following situation: one peanut in pile A, three peanuts in pile B, and one peanut in pile C [1,3,1]. By the strategy above, you would think that Bob could just remove all three peanuts in pile B, leaving two piles containing one peanut each. The situation is balanced - there are two coefficients of 1 - but if Bob did this, he would lose. Annie would take one of the last two peanuts, and Bob would take the last.

There's a special case that arises in our strategy when you get to a situation where all the piles have one peanut each, and in this situation the reverse applies. Bob wants to leave an odd number of single-peanut piles.

In practice, it's not difficult to spot. Just remember to look out for it towards the end of the game. When all the piles bar one have a single peanut, then either take all the peanuts from the final pile, or leave one peanut there - whichever leaves you with an odd number of single-peanut piles remaining.

In our example game, Bob took two peanuts, leaving Annie with three piles of one.

### And Finally

So there you have it. You've taught yourself binary, you've exercised your brain with some mental dexterity, you've learned how to play an absorbing game of strategy, and you've found out how to turn the tables on a scammer. Not bad for a day's work!

1Obviously, you'd need to play with at least four piles to have a total of four of any of the coefficients, unlike our example which only uses three piles.