# Variant of nim game with particular rules

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 ?

• See Wikipedia. – Emil Jeřábek supports Monica May 24 '18 at 13:37
• @EmilJeřábek Make an answer? – Yuval Filmus May 24 '18 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 '18 at 16:45

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.