Associated Topics || Dr. Math Home || Search Dr. Math

### Winning at NIM

```
Date: 07/23/98 at 04:19:30
From: Chris
Subject: Nim

Hi,

At the end of the term my maths teacher said he would win the game of
Nim every time, and he did! He said to go away and think about it, and
come back and beat him. He was almost sure that no one could beat
him. I have tried to work out a pattern or some other way of
guaranteeing victory, but to no avail. Can you help?

P.S - The winner is the last person to take the stick. The game
arrangement is in three rows, with 5 sticks in the first row, then
four in the next, and finally three in the last. Everything I have
tried brings me back to binary numbers. Is this right? Could you be as
fundamental as possible?
```

```
Date: 07/23/98 at 22:01:35
From: Doctor Jaffee
Subject: Re: Nim

Hi Chris,

you. There are a lot of different versions of the game of NIM, so I
need to know the rules of the game that you and your teacher are
playing.

Specifically, what is the maximumum and mininum number of sticks that
you can take on any turn? Also, can you take sticks from more than one
row on any given turn?

If you write back and provide this information for me, I think I can
help. Normally, the key to working out a good strategy in NIM games is
to work backwards. What does the game board look like at the end of a
game, the move before that, the move before that one, and so on? If you
take this approach you will notice that certain patterns develop that
will tell you that victory is imminent if you just follow the pattern.

- Doctor Jaffee, The Math Forum
Check out our web site! http://mathforum.org/dr.math/
```

```
Date: 07/25/98 at 05:15:54
From: Chris Tyrrell
Subject: Re: Nim

Dr. Math,

In reply, you can take as many sticks as you want in each turn, but
only from one line.

Hope this helps,
Chris
```

```
Date: 07/26/98 at 14:54:29
From: Doctor Jaffee
Subject: Re: Nim

Hi Chris,

All right! I think I can help you now. First, let's make sure I
understand the rules.

The game involves 12 sticks arranged in three rows, 5 in the first row,
4 in the second row, and 3 in the third row. There are two players and
each takes a turn picking one or more sticks from any one of the rows.
Whoever takes the last stick is the loser.

Now, let's set up some notation to make my explanation easier for me.
(5,4,3) represents the original setup of the game. For example,
(4,1,2) means there are 4 sticks in one of the rows, 1 in another row,
and 2 in the remaining row.

The suggestion I made in my previous reply to you was to work
backwards. Well, I did that and discovered that there are 6 losing
arrangements. These are arrangements that if it is your turn and you
are playing against your teacher, you are guaranteed to lose:

(1,1,1)  (0,2,2)  (3,2,1)  (3,3,0)  (4,4,0)  (5,4,1)

For example, if it is your turn and you have a (1,1,1) arrangement you
have to take exactly 1 stick, then your teacher will take 1, and you
are left with the last one. If you have (0,2,2) you can take 1 stick
from a row, then your teacher will take 2 sticks from the other row,
and you lose. If you took 2 sticks from a row, your teacher would take
1 from the other row and you would still lose.

If you have a (3,2,1) arrangement, no matter what you do your teacher
could transform it into (1,1,1), (0,2,2) or (0,0,1), all of which are
losing arrangements. Likewise with the other three arrangements. No
matter what you do, your teacher can transform it into one of the other
losing arrangements in just one turn.

So the key to your success is make sure your teacher has one of the
losing arrangements. The only way you can accomplish this is go first
and take 2 sticks from the 3 row, leaving your teacher with (5,4,1).
Then no matter what your teacher does you should be able to transform
it into another losing arrangement in one turn.

Play some practice games with your family and friends to try it out;
then when you are ready, take on your teacher. Good luck and let me
know how things go!

- Doctor Jaffee, The Math Forum
Check out our web site! http://mathforum.org/dr.math/
```
Associated Topics:
High School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search