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?

Improve this question
$\endgroup$
4
  • 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
    Commented Nov 25, 2017 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
    Commented Nov 25, 2017 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
    Commented Nov 25, 2017 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
    Commented Nov 25, 2017 at 22:52

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .