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,

I think I can help you out, but first I need some more information from 
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.

I'll be watching for your reply.

- 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/