Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

These are known as subtraction games; in general, for some set $S=\{s_1, s_2, \ldots s_n\}$ the game $\mathcal{S}(S)$ is the game where each player can subtract any element of $S$ from a pile. (So your simplified case is the game $\mathcal{S}(\{1\ldots B\})$) The nim-values of single-pile positions in these games are known to be ultimately periodic, and there's a pairing phenomenon that shows up between 0-values and 1-values, but generically there isn't much known about these games with $n\gt 2$. Berlekamp, Conway, and Guy's Winning Ways For Your Mathematical Plays has a section on subtraction games; as far as I can tell, it's still the canonical reference for combinatorial game theory. The Games of No Chance collections also have some information on specific subtraction games, and it looks like an article on games with three-element subtraction sets showed up recently on arxiv ( http://arxiv.org/abs/1202.2986 ); that might be another decent starting point for references into the literature.

share|improve this answer
add comment

You have analyzed the game correctly. Wikipedia lists it as "the subtraction game" under "Other variations of Nim".

share|improve this answer
    
However it is not a standard subtraction game, which is what my question is about. In my particular case, not all states of the pile are valid. –  NullOverNull Jul 2 '12 at 17:55
    
I don't know about a name, but you can use the Sprage-Grundy theorem to determine the winning positions and Nim values. It seems the valid removals will vary depending on the size of the pile. You will probably not see the nice periodicity that the basic game has. –  Ross Millikan Jul 2 '12 at 18:41
    
In my case, $V$ follows a recurrence. My issue is that I don't even know where to begin analyzing in order to develop a strategy that doesn't rely on brute scanning/trial and error/etc. –  NullOverNull Jul 2 '12 at 18:51
    
@NullOverNull Since the game is (ultimately) eventually periodic, once you find the period and saltus you have a strategy; and there are ways of knowing when you've found the period, but that period can be very large in terms of the subtraction-set (see, e.g., sciencedirect.com/science/article/pii/030439759500019S ). Are you at all familiar with the Sprague-Grundy theory of impartial games that Ross mentions? –  Steven Stadnicki Jul 2 '12 at 19:26
    
@StevenStadnicki I vaguely understand it as the distance from winning position (a grundy number of 1 meaning you're one step away from a winning position or something to this effect). I am also not sure about periods, since my set $V$ has an exponential recurrence –  NullOverNull Jul 2 '12 at 20:23
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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