2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Note $6_{10}=110_2$ $\endgroup$ – Mark Bennet Mar 9 '14 at 3:57
  • $\begingroup$ Yea, my mistake; I typed too fast...I'm so ashamed at myself for being a computer scientist haha. $\endgroup$ – audiFanatic Mar 9 '14 at 4:16
  • 1
    $\begingroup$ The core mistake in the question (as pointed out in zyx's answer) is that while this game is Nim-like and the means for computing the value of an overall position is to nim-sum the Grundy values of the single-piles, the game itself is not Nim in the standard sense, and the Grundy value of a single pile is not simply the number of sticks in a pile. $\endgroup$ – Steven Stadnicki Mar 9 '14 at 5:40
5
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ As an aside, I would say that there are more accessible resources than Winning Ways for most of the material contained within it. For impartial games alone, there's Tom Ferguson's "Game Theory", and for an introductory book on CGT, Lessons in Play will be an easier read, I feel. $\endgroup$ – Mark S. Mar 9 '14 at 22:17
  • $\begingroup$ Ah...that's what I was missing. I thought we were just xor-ing the size of the piles (which is the Grundy value of the starting positions of each pile anyway). I didn't realize I had to find new Grundy numbers. $\endgroup$ – audiFanatic Mar 10 '14 at 20:29
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So I would convert my piles to base 3 then? Or take $mod~3$ after taking the digital sum? $\endgroup$ – audiFanatic Mar 9 '14 at 4:20
  • $\begingroup$ every pile gives you a number equal to 0,1 or 2. Apply the nim addition to those numbers (this is what the addition theory says to do). $\endgroup$ – zyx Mar 9 '14 at 4:25
  • $\begingroup$ ok, so the first pile would become a pile of zero, second and third would become a pile of 1, and the last one would become a pile of 2? $\endgroup$ – audiFanatic Mar 9 '14 at 4:39
  • $\begingroup$ 2, 1, 1, 0. $\endgroup$ – zyx Mar 9 '14 at 5:00
  • $\begingroup$ Ok, but suppose I start with a different set of piles. Say I start with three sticks in pile 2 instead of 4 (and everything else remains the same)? I can't have fractional Grundy numbers. $\endgroup$ – audiFanatic Mar 9 '14 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.