7
$\begingroup$

Consider the following game:

There are a number of piles of stones. On each turn a player can remove as many stones he likes (at least 1) from up to $N$ piles (at least 1). It is allowed to remove a different amount of stones from each of the up to $N$ piles. The first player that can't move loses.

For $N=1$ we have the original game of nim with its well known optimal strategy.

For $N \geq$ number of piles the obvious optimal strategy is to remove all the stones.

What is the optimal strategy for $N=2,3,..$?

Extra question: What is the sprague-grundy value for these games?

$\endgroup$
  • $\begingroup$ "For N=1 we have the original game of nim with its well known optimal strategy." $$ $$ To get started, you can present the optimal strategy for $N=1$. This might help you or others to find an optimal strategy for the case $ N>1$ $\endgroup$ – callculus Sep 2 '14 at 13:19
  • $\begingroup$ That's a good question - I wish I had known the answer last week :). Wait, are you the Ward Beullens who also took part in hackerrank's weekly? $\endgroup$ – Hagen von Eitzen Sep 2 '14 at 13:19
  • $\begingroup$ The Sprague-Grundy theory says that amy position in any impartial game ( pf which this is an example) is equivalent to a single nim-heap, and provides a strategy. Check it out $\endgroup$ – MJD Sep 2 '14 at 13:20
  • $\begingroup$ @calculus The well-known strategy is to XOR all pile sizes and make a move that makes the XOR zero (if it is already zero, you lose). $\endgroup$ – Hagen von Eitzen Sep 2 '14 at 13:21
  • 1
    $\begingroup$ @MJD Then the real question is: Given heap sizes $n_1, \ldots, n_m$ and $N$, determine $n$ that is equivalent to this game. $\endgroup$ – Hagen von Eitzen Sep 2 '14 at 13:22
4
$\begingroup$

The winning strategy is described under section "Index-k Nim" in http://en.wikipedia.org/wiki/Nim.

In short: Instead of doing arithmetic in $Z_2^\infty$, you do it in $Z_{k+1}^\infty$ and choose a move that leaves you with $0$ as a result.

For example, let us consider $N=2$ and three piles of sizes $5,8,10$. The sizes in binary are $101$, $1000$ and $1010$. Their bitwise sum modulo $N+1 = 3$ is $2111$. Remove $3$ stones from the second and $5$ from the third pile to get new pile sizes $101,101,101$, whose mod $3$ sum is $0$.

$\endgroup$

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.