A game of nim is played with one pile of 30 tokens. The two player takes turns taking tokens off the pile. Whoever takes the last token wins.

To make the game a little more interesting, the rules have been changes slightly:
A player may take 1, 3, 4, or 5 tokens but not 2.

What is the best starting move and what is the general strategy?

If you are left with 1,3,4 or 5 you can win immediately.  If you are left with 2, you will lose as you're forced to take 1 and leave the opponent with 1.

How can you leave your opponent with 2? If you have 6 or 7, you can take away 4 or 5 and be on the winning path.

What if you have 8? You're forced to leave 7,5,4 or 3, giving your opponent the win, so 8 is a bad thing to get.  You can give it to your opponent by yourself having 9,11,12 or 13.  What about 10? If you've got that, you can give your opponent only 5,6,7 or 9, with which your opponent can win, so you don't want to be left with 10-- you want to leave your opponent with it.

Going on in this fashion we see we always want to leave the opponent with a number that is congruent to either 2 or 0 mod 8.

Clearly, leaving the opponent zero is the goal of the game. When you reduce the pile to zero you've won.  When you reduce the pile to a number congruent to 2 mod 8, the only choices your opponent has are to reduce the pile to 1, 7, 6 or 5 mod 8, none of which can win.  When you reduce the pile to a number congruent to 0 mod 8 (other than the winning 0 itself). You force the opponent to leave it congruent to 7, 5, 4 or 3 mod 8--again not a winning trail.

So, at the start of the game, you are presented with 30 tokens.  Take 4 to leave 26, which is 2 mod 8.  Then leave either 24 or 18, whichever is possible, etc., always leaving a number congruent to 0 or 2 mod 8.

Posted by Charlie on 2004-09-02 16:11:40