0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If you can take the objects from any pile you want, you can consider all the piles to be one pile with all the elements. Dennis Meng's solution exploits this. To deviate from the standard you need the rule to be take up to $N$ from any one pile. $\endgroup$ – Ross Millikan Oct 7 '13 at 4:38
  • $\begingroup$ @RossMillikan No...that's not what my solution touches on at all. My solution is for that latter case; when you're restricted to removing from one pile. If it's the former case (i.e. you can take from multiple piles at once, as long as the total removed is at most $N$), then the proof is much shorter (and the position would be losing iff the total sum of all stones is divisible by $N+1$, no nimsum required). $\endgroup$ – Dennis Meng Oct 7 '13 at 5:42
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ For how I got ideas: think of each pile as a separate game and use Sprague-Grundy theorem. Then note that finding the nimber of simultaneous games is done by xoring the nimbers of the individual games. Finding the actual strategy then isn't that much different from a constructive proof of a winning strategy for Nim. $\endgroup$ – Dennis Meng Oct 7 '13 at 4:25

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.