Winning a restricted game of Nim?

Question

Given the following piles, find the Grundy number of the initial position and make the first move in a winning strategy given that no more than two sticks may be removed from a pile at any time.

Pile 1 (2): $II$
Pile 2 (4): $IIII$
Pile 3 (4): $IIII$
Pile 4 (6): $IIIIII$

---

Obviously, the Grundy number for this arrangement (without restriction) is 4 (by digital addition, XOR-ing the number of sticks in each pile) as shown below:

$~~~ 010_2$
$\oplus100_2$
$\oplus100_2$
$\oplus110_2$
$---$
$~~100_2 => 4_{10}$

My guess would be to "hide" or disregard a certain number of sticks in the pile so that I can play as though (pretend) I were playing unrestricted nin. However, I'm unsure if this technique will result in the correct result. I'd appreciate any advice here.

Answer 1

There is a general rule - the mex rule - for computing Grundy values (or equivalent Nim heaps) in Nim-like impartial games. The moves you have available are take one stick or take two sticks. These lead to smaller positions whose values you already know. List those values and find the first number from $\{0, 1, 2, 3\dots \}$ which you cannot reach. This minimum excluded (mex) value is the one you want.

For a pile of zero the value is $0$

For a pile of one the only move is to zero, the value $0$ is excluded so the value is $1$

For a pile of two the moves are to one $(1)$ and zero $(0)$ so mex is $2$

For a pile of three there are moves to two $(2)$ and one $(1)$ so mex is $0$

For a pile of four there are moves to three $(0)$ and two $(2)$ so mex is $1$

$\dots$

The Grundy values when positions are combined are added using the Nim addition rule you know.

There is an extensive discussion of impartial games of various kinds in Winning Ways (Berlekamp, Conway and Guy).

Answer 2

For one pile, the $0$ positions are the multiples of $(2+1)$, and the G-values must all be $0,1$ or $2$, so $G(n)=(n \mod 3)$. The Nim addition theory then dictates the G values for the game with several piles.