# Ordered Nim game

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?

• 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). – Gro-Tsen Nov 25 '17 at 11:00
• 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. – Martin Rubey Nov 25 '17 at 13:01
• 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. – Alex Row Nov 25 '17 at 15:39
• 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. – Gerry Myerson Nov 25 '17 at 22:52

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.