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

combinatorial-game-theorygame theory

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?

Best Answer

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.

Related Question