2
$\begingroup$

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!

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

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.

$\endgroup$

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.