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?

(In reply to re: Solution - Embarrassed? by Bruce Brantley)

I think Bruce’s reasoning for why the pattern followed a cycle of 8, and why you want to force your partner into X mod 8 = 0 or 2, made sense. I was thinking about it on my own yesterday, and here’s the way I thought of it.

Ok, "normally" in these problems you are given a consecutive number of coins you could take away, starting with 1 ("you can only remove 1, 2, or 3 coins" like that). In those problems, I will call the maximum number of coins you can remove M. In those cases, the pattern follows a cycle of M+1, and the undesired state is to start your turn with X mod (M+1) = 0. As Bruce pointed out, that is because 0 is the winning state, so if you start your turn with 0, that really means that your opponent won on the previous turn.

So in this particular problem, M+1 is 6. However, since 2 was removed as a choice of coins to take, this changes things a little. In general, let’s call the value of the coin removed as a choice, R. I don’t know exactly how, but it seems that the pattern of the cycle follows "X mod (M+1 + R) = 0 or R."

Now this isn’t perfectly true. It worked when I checked R=1 (so I could only take 2, 3, 4, 5 coins). But not when I checked R=3 (I could only take 1, 2, 4, 5 coins). When R=3, the answer was actually "X mod R = 0."

I feel like "force your partner into having X mod (M+1 + R) = 0 or R coins" is close to the general answer, but not quit complete.

Posted by nikki on 2004-09-03 08:32:43