# Optimal strategy for this Nim generalisation?

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?

• "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$ – callculus Sep 2 '14 at 13:19
• 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? – Hagen von Eitzen Sep 2 '14 at 13:19
• 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 – MJD Sep 2 '14 at 13:20
• @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). – Hagen von Eitzen Sep 2 '14 at 13:21
• @MJD Then the real question is: Given heap sizes $n_1, \ldots, n_m$ and $N$, determine $n$ that is equivalent to this game. – Hagen von Eitzen Sep 2 '14 at 13:22

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