Variation of Nim, where one has to divide a pile into any number of piles.

Question

I am learning the basics of combinatorial game theory (impartial games). After learning about decompose a game into the sum of games, I feel comfortable with games that can divided into the sum of 1 pile games. The situation is more or less clear to me: I have to find the game graph, calculate the Sprague-Grundy values and use them to find the solution to a game.

But I do not really know what to do in case when I can't decompose a game in 1 pile games. Here is an example:

You have piles of stones, people alternate turns, person who can't make a move loses. During the move, a player can select any one of the piles divide the stones in it into any number of unequal piles such that no two of the newly created piles have the same number of stones.

---

I have huge problem in analyzing the 1 pile subgame (calculating grundy values for the pile of $1, 2, 3, ... n$ stones in the pile), because after each move 1 piles is divided into more piles.

How should I analyze such games?

Answer 1

It’s not hard to use Jyrki’s suggestion to make a table of Sprague-Grundy values of small single heaps:

$$\begin{array}{rcc} \textbf{heap size}:&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\ \textbf{S-G value}:&0&0&0&1&0&2&3&4&0&5&6&7&8&9&10&11&12 \end{array}$$

• For $n=6$ the possible splits are $\langle 5,1\rangle,\langle 4,2\rangle$, and $\langle 3,2,1\rangle$, with S-G values $2$, $0$, and $1$, respectively, so the S-G value of $6$ is $3$.
• For $n=7$ the possible splits are $\langle 6,1\rangle,\langle 5,2\rangle,\langle 4,3\rangle$, and $\langle 4,2,1\rangle$, with respective values $3$, $2$, $1$, and $0$, so the value of $7$ is $4$.
• For $n=8$: $\langle 7,1\rangle,\langle 6,2\rangle,\langle 5,3\rangle,\langle 5,2,1\rangle$, and $\langle 4,3,1\rangle$, with respective values $4$, $3$, $2\oplus 1=3$, $2$, and $1$, so the value of $8$ is $0$.
• For $n=9$; $\langle 8,1\rangle,\langle 7,2\rangle,\langle 6,3\rangle,\langle 5,4\rangle,\langle 6,2,1\rangle,\langle 5,3,1\rangle$, and $\langle 4,3,2\rangle$, with values $0$, $4$, $3\oplus1=2$, $2$, $3$, $2\oplus 1=3$, and $1$, so the value of $9$ is $5$.
• For $n=10$: $\langle 9,1\rangle,\langle 8,2\rangle,\langle 7,3\rangle,\langle 6,4\rangle,\langle 7,2,1\rangle,\langle 6,3,1\rangle,\langle 5,4,1\rangle,\langle 5,3,2\rangle$, and $\langle 4,3,2,1\rangle$, with respective values $5$, $0$, $4\oplus1=5$, $3$, $4$, $3\oplus1=2$, $2$, $2\oplus 1=3$, and $1$, so the value of $10$ is $6$.
• For $n=11$ the values of the reachable positions are $6,5,1,4,1,0,5,3,2,2,3$, so the value of $11$ is $7$.
• For $n=12$ the values of the reachable positions are $7,6,4,0,6,5,1,4,1,5,3,3,2,2$, so the value of $12$ is $8$.
• For $n=13$ the values of the reachable positions are $8,7,7,5,2,7,6,4,0,6,1,2,5,3$, so the value of $13$ is $9$.
• For $n=14$ the values of the reachable positions are $9,8,6$, $6,7,3$, $7,7,5$, $2,7,4$, $0,6,5$, $0,1$, $4,1,3$, so the value of $14$ is $10$.
• For $n=15$ the values of the reachable positions are $10,9,9$, $7,4,6$, $4,8,6$, $6,7,3$, $7,5,2$, $7,1,7$, $1,4,0$, $6,2,3$, so the value of $15$ is $11$.
• For $n=16$ the values of the reachable positions are $11,10,8$, $8,5,5$, $1,9,9$, $7,4,6$, $4,6,6$, $7,3,4$, $3,6,6$, $7,5,2$, $7,5,0,2$, so the value of $16$ is $12$.

I had hoped that the S-G value of $16$ would be $0$, suggesting a pattern of values increasing by $1$ but dipping to $0$ at each power of $2$. Since that failed, I have no reasonable guess at the actual pattern.

It’s probably worth investigating the possibility that for $n\ge 9$ the S-G value of a heap of $n$ is simply $n-4$; I do intend to give it some thought.

Answer 2

As Jyrki commented, moves in this game do decompose piles into sums of piles, and the xor rule still applies when you have a sum of more than two piles.

With a little Mathematica code just using the mex and xor rules for the Sprague-Grundy values, I found that the values for a single pile from size $1$ to size $70$ are: $0,0,1,0,2,3,4,0,5,6,7,\ldots,66$. In particular, the value for a single pile of size $n$ (where $n>9$) appears to be $n-4$. This sort of pattern makes sense because as the numbers grow, there are so many ways to partition the pile that you can achieve every previous number as the xor of the values you can reach.

However, I haven't been able to see an obvious pattern in the winning moves, so I'm not sure how to prove that this pattern continues forever.

---

code:

moves[n_] := moves[n] = 
  Map[If[Union[#] == Sort[#] && Length[#] > 1, #, Nothing] &, 
   IntegerPartitions[n]]; 
mex[list_] := mex[list] = 
  Do[If[Not[MemberQ[list, i - 1]], Return[i - 1]], {i,Length[list] + 1}]; 
nimber[n_] := nimber[n] = 
  mex[Map[Apply[BitXor, Map[nimber, #]] &, moves[n]]];

---

Edit:

Using cgsuite, we can get much further. If we restrict the rules to say that you can decompose a pile into at most five piles, then the Sprague-Grundy values can be calculated very efficiently by cgsuite code: hr:=game.heap.HeapRules.MakeRules("&60;!."); hr.NimValues(500)

With this, we see that splitting into at most five piles is enough for the pattern mentioned above to persist all the way up to size $499$ with value $495$. Restricting to at most four piles puts a 0 between 12 and 13, but continues an $n-5$ pattern thereafter all the way up to an initial pile size of $499$ as well. (At most three piles gives too few options for a simple pattern).