0
$\begingroup$

Find the Grundy number of the initial position and make the first move in a winning strategy for the following game:

In a pile there are two red balls, four green balls, four blue balls, and six white balls. A player can take a (non-zero) number of balls of same color: one red, or one or two green, or one, two, or three blue, or up to four white balls.

How do I do this? I've only ever done Nim games with multiple piles; never have I had one pile with multiple types of objects in one pile.

$\endgroup$
1
$\begingroup$

HINT: Since in any move you can take only balls of one color, you really have four separate piles:

$$\begin{array}{ccc} &&&\circ\\ &&&\circ\\ &\color{green}\bullet&\color{blue}\bullet&\circ\\ &\color{green}\bullet&\color{blue}\bullet&\circ\\ \color{red}\bullet&\color{green}\bullet&\color{blue}\bullet&\circ\\ \color{red}\bullet&\color{green}\bullet&\color{blue}\bullet&\circ \end{array}$$

The red pile is one-heap takeaway with a limit of $1$ ball per move; the green pile is one-heap takeaway with a limit of $2$ balls per move; the blue pile is one-heap takeaway with a limit of $3$ balls per move; and the white pile is one-heap takeaway with a limit of $4$ balls per move. Your game is in effect the sum of these four simple games.

$\endgroup$
  • $\begingroup$ So is the initial position for red, green, blue, and white equal to $0, 1, 1, 1$ respectively? And so then the Grundy number of the initial position is eual to $1$? One good first move would be taking one from the green pile, for example? $\endgroup$ – BrianW May 2 '16 at 21:30
  • $\begingroup$ @BrianW: I get $0,1,0,1$, meaning that there is no winning move. $\endgroup$ – Brian M. Scott May 2 '16 at 21:39
  • $\begingroup$ Yep, I mistakenly took blue and green to have the same conditions. Makes sense. Thanks! $\endgroup$ – BrianW May 2 '16 at 21:41
  • $\begingroup$ @BrianW: You’re welcome! $\endgroup$ – Brian M. Scott May 2 '16 at 21:41

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.