Partition Game

Alice and Bob are playing a game as follows. Originally there are $n > 1$ piles containing $s$ stones each. Alice starts by taking the first turn and at each step, the player chooses one pile and discards the other piles. Then that player divides the stones from that one pile into $n$ piles, such that each pile still contains at least 1 stone. The player that cannot move loses.

Determine all $s$ such that Alice has a winning strategy

Solution

We classify every natural numbers into winning numbers or losing numbers with the following recursion: The numbers $1, \dots, n-1$ are losing numbers. If a number can be partitioned into losing numbers, then it's a winning number. Otherwise it's a losing number. In other words, any given partition of a losing number must contain a winning number.

Now the game is a standard Sprague-Grundy game. If a player receives a state where one pile contains a winning number, then that state is a winning state. For example, $n$ is a winning number because the player can split it into ones, regardless of what the other numbers in the pile are. If a player receives a state where all piles are losing numbers, then it's a losing state.

Let $m=n-1$. Now we establish the base cases. $1, \dots, m$ are losing numbers. Then $n$ can be partitioned into all ones, and $mn$ can be partitioned into all $m$'s. It's easy to show that all the numbers in between can also be partitioned into summands between $1$ and $m$ inclusive, so $n,\dots,mn$ are winning numbers.

Now we claim: Let $x \equiv p \mod mn$ then $x$ is a winning number if and only if $p = 0$ or $p \geq n$, and it is a losing number if and only if $p \in [1,m]$. We prove it by induction on $k = \lceil x / mn \rceil$. The case of $k = 1$ is proven by the base case above.

Now suppose we have a number $x$ with residue in $[1,m] \mod mn$ and there is a way to partition this number into $n$ summands, all while staying within $[1,m] \mod mn$. The smallest sum (in the residue space) that can be attained is $n$, and the largest sum is $mn$, and they are all outside of $[1,m]$, a contradiction. So some of the summands must have residue $0$ or $\geq n \mod mn$. Let $y$ be this summand. Note that $ \lceil y / mn \rceil < \lceil x / mn \rceil$ in each of these cases. So $x$ is a losing number by induction hypothesis.

Now suppose we have a number $y$ divisible by $mn$, then we can partition it into $n$ numbers all having residue $m$. The easiest is of course to have the first $m$ terms $m$ and have the last term $y - m^2 = kmn - m^2 = (k-1)mn + m$. Each of these numbers are losing numbers with less quotient than $y$, so $y$ is a winning number.

Next, suppose we have $y$ with residue $[n, mn-1]$. Using the same argument as above, we can see that it can always be decomposed into the sum of $n$ numbers with residue $[1,m]$. However, the quotient of the summands are not necessarily less than $y$, but we have proved that the set in $[1,m]$ with quotient $k$ are losing numbers as well.