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(2): Solution - generalized? by nikki)

Some more thoughts on the general solution - I think I have it!:

The reason that R=3 didn’t work (if you don’t know what I’m talking about, see some previous posts of mine) is because it is greater than half of M = 5. Let’s see if I can explain this better.

Ok, we’ve already looked at the given problem. Let’s look at a slightly modified problem. Let’s say we can only take 2, 3, 4, or 5 coins. This means that M = 5 and R=1. According to my generalized solution, I would predict that the undesirable states are X mod 7 (from M+1+R) = 0 and 1 (from R), and I should be "safe" during X mod 7 = 2, 3, 4, 5, or 6. So, let’s say you are faced with X coins on your turn. The amount you should take away is either (X mod 7) – 0 or (X mod 7) - 1, and the answer must always be 2, 3, 4, or 5. Let’s look at each case and see if there is a problem with my prediction.

X mod 7 = 2 : 2-0 = 2, 2-1 = 1. So you’d take 2.
X mod 7 = 3 : 3-0 = 3, 3-1 = 2. So you’d take 2 or 3.
X mod 7 = 4 : 4-0 = 4, 4-1 = 3. So you’d take 3 or 4.
X mod 7 = 5 : 5-0 = 5, 5-1 = 4. So you’d take 4 or 5.
X mod 7 = 6 : 6-0 = 6, 6-1 = 5. So you’d take 5.

Well, my predictions seem fine.

Now let’s look at another slightly modified problem. Now we can only take 1, 2, 4, or 5 coins. This means that M = 5 and R=3. According to my generalized solution, I would predict that the undesirable states are X mod 9 (from M+1+R) = 0 and 3 (from R), and I should be "safe" during X mod 9 = 1, 2, 4, 5, 6, 7 or 8. So, let’s say you are faced with X coins on your turn. The amount you should take away is either (X mod 9) – 0 or (X mod 9) - 3, and the answer must always be 1, 2, 4, or 5. Let’s look at each case and see if there is a problem with my prediction.

X mod 9 = 1 : 1-0 = 1, 1-3 = -2. So you’d take 1.
X mod 9 = 2 : 2-0 = 2, 2-3 = -1. So you’d take 2.
X mod 9 = 4 : 4-0 = 4, 4-3 = 1. So you’d take 1 or 4.
X mod 9 = 5 : 5-0 = 5, 5-3 = 2. So you’d take 2 or 5.
X mod 9 = 6 : 6-0 = 6, 6-3 = 3. PROBLEM!
X mod 9 = 7 : 7-0 = 7, 7-3 = 4. So you’d take 4.
X mod 9 = 8 : 8-0 = 8, 8-3 = 5. So you’d take 5.

In the other problem, there were times when one of the subtractions (Xmod7-0 or Xmod7-1, for example) equaled 1, which is R. But that was ok because the other subtraction yielded a legal move. See X mod 7 = 2, for example.

Also, there were times when one of the subtractions equaled something higher than 5, which is M, like 6, 7, or 8. But also was ok because the other subtraction yielded a legal move. See X mod 7 = 6 for an example.

However, with X mod 9 = 6 (remember, 6 = M+1), we have a problem. We either get a number that is too big, outside of our legal moves, or we get a number that is equal to R, also not a legal move. Why does this happen? Well, once you start looking at X mod (M+1+R) > M, one of the subtractions is always X mod (M+1+R) – 0, and will always equal X mod (M+1+R), which we already said is greater than M. So we must rely on the other subtraction, X mod (M+1+R) – R. This will be a problem when X mod (M+1+R) = 2R.

So the problem state in my general solution will always be when M < X mod (M+1+R) = 2R, or when M < 2R, which means when R > M/2.

So here is my revised solution:

Given a problem, where you have a series of consecutive integers that you are allowed to remove starting at 1 (so call the series 1 through M), EXCEPT for one integer in the set which we will call R.

If R =< M/2, then the strategy is to take coins such that you leave your opponent with X coins such that X mod (M+1+R) = 0 or X mod (M+1+R) = R.

If R > M/2, then the strategy is to take coins such that you leave your opponent with X coins such that X mod R = 0.

What do you guys think?  Hopefully I was coherent.

Posted by nikki on 2004-09-03 10:42:58