Multi-Pile NIM where you can only take up to N objects strategy?

Question

What is a strategy for a multi-pile nim game, with each pile having a different number of objects. Further, on any turn you can only take up to N objects. Most posts about nim involve a multi-pile game where you can take any number of objects.

Answer 1

Suppose there are $k$ piles, which have $p_1, p_2, .., p_k$ stones.

Let $r_i$ be the remainder when $p_i$ is divided by $N + 1$ (That is, $p_i \equiv r_i \pmod{N + 1}$ and $0 < r_i < N+1$). I claim that the position is a P-position (i.e. a losing position) iff $$\displaystyle\bigoplus_{i=1}^k r_i = 0$$.

(That is, the bitwise xor of all of the remainders mod $N + 1$ is 0).

To prove this, I need to show that

1. If the game state is currently such that the above left-hand side is indeed 0, then it will become nonzero no matter what the next move is (This fulfills the requirement that every move from a P-position results in an N-position.)
2. If the game state is currently such that the above left-hand side is nonzero, then there exists a move such that it will become zero (This fulfills the requirement that every N-position has a move that goes to a P-position.)

Lemma 1: Proof of the first statement.

Suppose the result of the left-hand side is 0. First, note that since you may only remove up to $N$ stones from a pile, any move must change the remainder $\bmod{N + 1}$ for that pile. Suppose the move removed some number from pile $i$, so that its size $\bmod{N + 1}$ was $r_i$ before and is now $r'_i$.

The new result of the bitwise xor of all the remainders is now $r_i \oplus r'_i$. (Take the original equation, $\oplus$ both sides with $r_i \oplus r'_i$, and note that the operation is commutative, associative, and $x \oplus x = 0$ plus $x \oplus 0 = x$ is true for all valid $x$). Since we've already established that $r_i \neq r'_i$, $r_i \oplus r'_i \neq 0$, and we're done.

Lemma 2: Proof of the second statement.

Now, suppose the left-hand side is some nonzero value $s$. Write $s$ in binary, and locate a pile with $p_i$ elements such that its remainder $\pmod{N+1}$ (for consistency, call it $r_i$) also contains a 1 in that location when written in binary. Note the result when you xor $r_i$ and $s$:

r_i      : ...1...
s        :    1...
r_i xor s: ...0...

Note that whatever the ... was to the left of $r_i$ is shared by $r_i \oplus s$ as well, and thus we know that $r_i \oplus s < r$. Thus, we can easily remove stones from the $i$th pile so that its remainder is now $r_i \oplus s$ instead of $r_i$. A similar argument to what we did in Lemma 1 for computing the new results shows that such a move would result in the xor of the remainders once again becoming 0, and we're done.

Thus, I've proved both statements, and thus we can conclude that the position is a P-position (i.e. a losing position) iff $$\displaystyle\bigoplus_{i=1}^k r_i = 0$$.

(where $p_i \equiv r_i \pmod{N + 1}$ and $0 < r_i < N+1$ for all $i$, as defined earlier).