Let's say we have the following rule for that particular Nim game: You have multiple heaps, and you have to remove 1,2 or 3 sticks (not more) from a SINGLE choosen heap. The player who pick up the last stick LOSES. (misere game). Is there an algorithm which solves this variant of Nim game ?

Thanks in advance!

  • See Wikipedia. – Emil Jeřábek May 24 at 13:37
  • @EmilJeřábek Make an answer? – Yuval Filmus May 24 at 16:16
  • Not sure if I get it... First of all, I have to reduce the size of all heaps modulo k+1. Only after that, I can compute the Nim-sum and if that sum is equal to 0 I have to pick up k sticks from a heap ? Am I right ? – QBl May 24 at 16:45
up vote 1 down vote accepted

The following answer solves your game under normal play when there is a single heap. You can accommodate multiple heaps using Sprague–Grundy theory. Using a very similar approach, you can also handle misère rules.

You can solve combinatorial games by calculating the winning and losing positions recursively, using the following algorithm (for your special case):

for n from 0 to infinity:
   set Win[n] to True if n ≥ 1 and Win[n-1] is False
   set Win[n] to True if n ≥ 2 and Win[n-2] is False
   set Win[n] to True if n ≥ 3 and Win[n-3] is False
   otherwise, set Win[n] to False

Here are some empirical results, starting at $n=0$:

False, True, True, True, False, True, True, True, False, True, True, True

The pattern repeats, so one can conjecture that $Win[n]$ is true iff $n$ is not a multiple of 4. It is not hard to prove this guess by induction. Clearly 0 is a losing position, and 1,2,3 are winning positions since we can remove 1,2,3 (respectively) to get to 0. Now 4 is a losing position, since whatever we remove gets us to one of the winning positions 1,2,3. As before, 5,6,7 are winning positions, since we can get down to 4. And so on.

In the same way, you can compute the Sprague–Grundy function, which is $g(n) = n \bmod 4$. This allows you to solve the multiple heap version of this game.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.