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?

I really really stink at these problems. However, as I try to grow mentally, I will take a stab at it, even at the risk of embarrassing myself.

They way I think is backwards, starting at the end of the game and seeing when it is desirable for there to be x coins at the beginning of your turn or your partner's turn, keeping in mind that your partner knows this information as well.

1: Clearly you want this on your turn. You just take the last one and win.

2: You want that to be on your opponent's turn. S/he can't take 2 so s/he will be forced to take one, leaving you with the last one to take.

3, 4 or 5: You want that to be on your turn. Then you'll just take them and win.

6, 7: You want this to be on your turn. Then you can take 4 or 5 coins, leaving your partner with 2 (see above).

8: You want this to be your opponent's turn. They will be forced to leave 7, 5, 4 or 3 coins, which are all good for you.

9: You don't want this to be your opponent's turn! They could just take 1, leaving you with the undesirable amount of 8. So you want this to be your turn so you can force THEM into having 8, leaving you home free.

10: You want this to be your opponent's turn. They will be forced to leave 9, 7, 6 or 5 coins, which are all good for you.

11, 12, 13: You don't want this to be your opponent's turn! They could leave you with the undesirable amount of 8 or 10. So you want this to be your turn so you can force THEM into having 8 or 10, leaving you home free.

14, 15: You want this to be on your turn. Then you can take 4 or 5, leaving your opponent with 10, leaving you home free.

16: You want this to be your opponents turn. They will be forced to leave 15, 13, 12 or 11, which are all good for you.

Ok, I am finally seeing the pattern. On your turn, you want to take enough coins to leave X coins, where Xmod8 = 0 or 2. Sometimes you will have a choice, like if there are 11 or 13 at the beginning of your turn, you could leave either 10 or 8.

However, I don't know how the restrictions of taking 1, 3, 4, or 5 coins turns into "always leave X coins such that Xmod8 = 0 or 2." Like how does it follow a pattern of 8? And why 0 and 2? I have no idea. Anyone else?

Anyways, the answer the to actual problem is that you want it to be your turn (since 30mod8 is 6, not 0 or 2), and you should take 4 coins, leaving your partner with 26 (26mod8 = 2). From their, no matter how many coins your partner takes, always take enough such that you leave X following the rule that Xmod8 = 0 or 2.

I guess I didn't stink quit as badly as I thought I would =)

(fixed a tiny math error... oopsies!)

Edited on September 2, 2004, 4:39 pm

Posted by nikki on 2004-09-02 16:29:30