A variation on NIM game

Question

Problem: We have two heaps of coins with 100 and 99 coins. Two players take some coins alternately, either at least one, at most 10, from the first one, or at least one, at most 9 from the second. The winner is who takes the last coin. How shall the game be played to win?

I think this is supposed to be solve using NIM strategy and Grundy numbers. Some hints on what general strategy to use on these problems would be nice. Also, an in-depth analysis of the problem would be helpful as a model that would allow me to approach other similar problems.

Answer 1

Hint: Start by computing the Grundy numbers for each heap individually. There are simple related formulas for them. Then you want the Grundy numbers of the two heaps to be equal so they sum to $0$.

Answer 2

First compute the Grundy number, using the mex formula, for the heap of size $n$ and moves 1 to 10. This is a recursive process, which is periodic (in this case) with period 11: $\operatorname{mex}(n)=n \pmod{11}$.

Then for the heap with moves $1$ to $9$ we get a period of $10$ and values $\operatorname{mex}(n)=n \pmod{10}$.

It's simple to write a small program to do this, or make a table by hand.

So $\operatorname{mex}(100)=1$ for the first heap and $\operatorname{mex}(99)=9$ for the second. So the first player wins by making the value of the first heap $9$ (moving to $97$) so that the total value is $0$ (this is a xor-sum of heaps, recall) or by making the second heap value $1$, by moving to $91$...