4
$\begingroup$

Consider this basic example of subtraction-based Nim before I get to my full question:

Let $V$ represent all valid states of a Nim pile (the number of stones remaining):

$V = 0,1,2,3,4,5,6,7,8,9,10$

Let $B$ be the bound on the maximum number of stones I can remove from the Nim pile in a single move (minimum is always at least 1):

$B = 3$

Optimal strategy in a two-player game then is to always ensure that at the end of your turn, the number of stones in the pile is a number found in $V$, and that it is congruent to $0$ modulo $(B+1)$. During my first move I remove 2 stones because $8$ modulo $4$ is $0$.

My opponent removes anywhere from 1-3 stones, but it doesn't matter because I can then reduce the pile to $4$ because $4$ modulo $4$ is $0$. Once my opponent moves, I can take the rest of the pile and win.

This is straightforward, but my question is about a more advanced version of this, specifically when $V$ does not include all the numbers in a range. Some end-states of the pile are not valid, which implies that I cannot find safe positions by applying the modulo $(B+1)$ rule.

Does this particular variant of Nim have a name that I can look up for further research? Is there another way to model the pile?

3 Answers 3