9
$\begingroup$

Consider the following variant of Nim:

There are two players and $n$ piles of stones, with sizes $a_1,\dots,a_n$, such that $a_i\leq a_j$ for any $i<j$.

A move consists of removing a positive number of stones from any pile, such that inequalities are preserved.

A player loses if all piles are empty.

What are the winning positions, or, more generally, what is the Sprague-Grundy value of a position?

$\endgroup$
  • 3
    $\begingroup$ An equivalent presentation is to use the $b_i := a_i-a_{i-1}$ instead, in which case the rule is that a player, instead of removing stones from one line, can just move them down to the next line (except that stones removed from the last line disappear). $\endgroup$ – Gro-Tsen Nov 25 '17 at 11:00
  • 2
    $\begingroup$ This is now findstat.org/St001055. It seems that there are some related statistics: for example, findstat.org/St000835 is zero provided that the partition is a losing position. $\endgroup$ – Martin Rubey Nov 25 '17 at 13:01
  • 2
    $\begingroup$ Using this statistics we can guess that grandy function of sequence can be calculated in such way: If n is even then $g=\oplus_i a[2i+1]-a[2i]$. if not then $g$=smallest element $\oplus$ grandy function of the remaining part. Only proof of it is left. $\endgroup$ – Alex Row Nov 25 '17 at 15:39
  • 1
    $\begingroup$ Not explicitly stated, but I take it the two players take turns, and a player loses if all the piles are empty when it is her turn to play. $\endgroup$ – Gerry Myerson Nov 25 '17 at 22:52
9
$\begingroup$

As Alex conjectures in a comment, the Grundy value is $$(a_n-a_{n-1}) \oplus (a_{n-2}-a_{n-3}) \oplus \cdots \oplus (a_2-a_1)$$ if $n$ is even, or $$(a_n-a_{n-1}) \oplus \cdots \oplus (a_3-a_2) \oplus a_1$$ if $n$ is odd.

To see this, let $b_i=a_i+i$, and place checkers in the spaces $b_1,b_2,\dots,b_n$ on a half-infinite strip. On your turn, you may move a checker any distance towards the end of the strip, without passing through a square occupied by another piece.

This is the "Silver Dollar game with No Silver Dollar": the piles are the gaps between alternating pairs of pieces. Any move to increase the size of a pile is immediately reversible, so the Grundy values are the same as in Nim.

$\endgroup$

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.