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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.