# Splitting Stacks Nim

A game is played with two players and an initial stack of $n$ pennies ($n\geq 3$). The players take turns choosing one of the stacks of pennies on the table and splitting it into two stacks. When a player makes a move that causes all the stacks to be of height $1$ or $2$ at the end of his or her turn, that player wins. Which starting values of $n$ are wins for each player?

For all the values I've tested, if it's even the first player wins and if it's odd the second player wins. If it's even, then the piles must be split into two evens or two odds. If it's two evens, the next player wins one of the splits recursively but the first player wins the other one (so the first player wins). If it's odd, the opposite happens (the second player recursively 'loses' both piles). If it's odd, then it must be split into one odd and one even pile, so the second player can choose to lose the odd pile and so win the even pile. BUT this doesn't take into account the fact that when you have a pile of $1$s and $2$s, that is considered finished for a pile of $n$, but when there is more than one pile, then you can still split the $2$s into $1$s and so delay your turn.

So what strategy works for all values that guarantees a win for one of the players?

-
This is an impartial game, and will be pretty easy to analyze with Sprague-Grundy theory. I wrote a tutorial here if you are interested. – MJD Aug 1 '13 at 16:21
The first player wins a stack of $3$ by splitting it into $2$ and $1$, and a stack of $4$ by splitting it as $2$ and $2$. The second player wins a stack of $5$, which splits as $2, 3$ (move to $2,2,1$) or $(4,1)$ also move to $2,2,1$. The first player wins even stacks by splitting them in two and then mirroring the oponent's move. – Mark Bennet Aug 1 '13 at 16:31

The first player wins if and only if you start with $1$, $3$, or an even number of pennies.

Like many nim-variants, this game has a simple condition that you win with, because you can always guarantee that you return to it on your turn until you reach an "end game":

Let $n$ be the number of stacks with an even number of pennies. You can win if and only if $n$ is odd at the beginning of your turn (or if you can win immediately on that turn by breaking up the last group of 3 or 4).

To see that you can always maintain this condition, consider how moves change $n$:

-Splitting an odd stack yields an even stack and an odd stack, increasing $n$ by 1.

-Splitting an even stack into two even stacks increases $n$ by 1.

-Splitting an even stack into two odd stacks decreases $n$ by 1.

In all these cases, the parity of $n$ changes. Thus the parity of n changes each turn, and so if it's odd at the start of your turn it will be even on your opponent's turn and odd on your turn again, ie it will be odd at the beginning of all your subsequent turns.

Now we just have to examine the "end game": How to avoid giving your opponent a position where they can win. If you could give them such a position, it means you could hand them a position with only one stack of more than 2 pennies: either a stack of 3 or 4. Assuming you can't win outright on your turn, this means the beginning of your turn is one of a few cases. We just need to enumerate them and show you can always win, assuming $n$ is odd:

Case 1 - There are $2$ stacks of $3$ (thus an odd number of stacks of $2$): Obviously whoever splits the first stack of $3$ loses, so you take turns splitting stacks of $2$. Since there's an even number of them at the end of each of your turns, you'll eventually have zero at the end of your turn, forcing your opponent to split one of the stacks of $3$. You win by splitting the other.

Case 2 - There's $1$ stack of $3$ and $1$ stack of $4$ (thus an even number of stacks of 2): Remove $1$ penny from the stack of $4$, forcing your opponent to split a stack of $2$ or let you win, reducing this to case 1.

Case 3 - There are two stacks of $4$ (thus an odd number of stacks of $2$): Remove a penny from one of the stacks of $4$. Your opponent will be forced to either remove a penny from the other stack of $4$, reducing to case 1, or split a stack of size $2$, reducing to case $2$.

Case 4 - There's a single stack of $5$ (thus an odd number of stacks of $2$): Whoever splits the stack of $5$ will lose, so you'll both be splitting the stacks of $2$. But since there's always an even number at the end of your turn, you'll split the last one and win.

Case 5 - There's a single stack of $6$, (thus an even number of stacks of $2$): Split the stack of $6$ into two stacks of $3$. Your opponent must split a stack of size $2$ or let you win, reducing to case 1.

This shows that if $n$ is odd at the beginning of your turn, you always have a move that doesn't let your opponent win, so eventually you'll win.

Interestingly, this means that any non-stupid strategy is optimal - as long as you don't let your opponent win on the next turn (and you win on your turn if you can), you'll end up winning the game. So you can't really "mess up" this game in a non-obvious way, unlike traditional nim.

-
But a single stack of $3$ is a first player win, as they only move to $2+1$ wins immediately. Your argument would be correct if the end condition were all $1$'s – Ross Millikan Aug 2 '13 at 18:34
Ha, you caught me in an endgame edge-case! Similarly, a stack of 4 and a stack of 2 is a win for the current player. The "only if" part of the statement only holds if you can't win immediately, just as the alternate phrasing (you can always win if you leave an even number of even stacks) only holds if your opponent can't win immediately. I'll update the statement to reflect this. – MartianInvader Aug 2 '13 at 18:41
@RossMillikan But if it wasn't clear from my previous comment, I'm pretty sure the argument is still correct - if there's more than one turn remaining, the player who has the odd number of even stacks at the beginning of his turn will win, and the only strategy he needs is to not hand the opponent a position where he immediately wins. – MartianInvader Aug 3 '13 at 0:02
What if you can only split a stack into $K$ stacks each time? (The constraint of each newly-resultant stack having at least number of pennies $\geq 1$ is still present.) – Max Li May 30 at 0:04

Here for reference is a table of nim-values for every nontrivial position with less than 12 pennies. Piles of size 1 have been omitted. A nim-value of 0 indicates a position that is a win for the player who moves to it; any other value indicates a position that is a win for the next player to move.

$$\begin{array}{lr} 3 & 1 \\ \hline\\ 4 & 2 \\ \hline\\ 3,2 & 2 \\ 5 & 0 \\ \hline\\ 4,2 & 1 \\ 3,3 & 0 \\ 6 & 2 \\ \hline\\ 3,2,2 & 1 \\ 5,2 & 2 \\ 4,3 & 2 \\ 7 & 0 \\ \hline\\ 4,2,2 & 2 \\ 3,3,2 & 2 \\ 6,2 & 0 \\ 5,3 & 0 \\ 4,4 & 0 \\ 8 & 1 \\ \hline\\ 3,2,2,2 & 2 \\ 5,2,2 & 0 \\ 4,3,2 & 0 \\ 7,2 & 1 \\ 3,3,3 & 0 \\ 6,3 & 1 \\ 5,4 & 1 \\ 9 & 0 \\ \hline\\ 4,2,2,2 & 1 \\ 3,3,2,2 & 0 \\ 6,2,2 & 2 \\ 5,3,2 & 1 \\ 4,4,2 & 2 \\ 8,2 & 0 \\ 4,3,3 & 1 \\ 7,3 & 0 \\ 6,4 & 0 \\ 5,5 & 0 \\ 10 & 1 \\ \hline\\ 3,2,2,2,2 & 1 \\ 5,2,2,2 & 2 \\ 4,3,2,2 & 2 \\ 7,2,2 & 0 \\ 3,3,3,2 & 1 \\ 6,3,2 & 0 \\ 5,4,2 & 0 \\ 9,2 & 1 \\ 5,3,3 & 0 \\ 4,4,3 & 0 \\ 8,3 & 1 \\ 7,4 & 1 \\ 6,5 & 1 \\ 11 & 0 \\ \end{array}$$

-
All sorts of questions are raised - aside from 6 pennies in two piles, the outcome seems to be determined by the number of pennies and the number of piles, though it isn't a simple parity thing. And the values remain low - is the maximum value $2$ or can it be higher? Do these patterns persist? – Mark Bennet Aug 1 '13 at 18:19
I checked all the positions up to 40 or so pennies for any with a nim-value above 2, and there were none. – MJD Aug 1 '13 at 18:55
I'm thinking that there might be an explicit strategy for odd positions, which could be established by induction. e.g. can the winning player avoid increasing the number of piles (ie take one from a pile) except in exceptional end positions? – Mark Bennet Aug 1 '13 at 19:02
MJD: is the nim-value actually determined by the number of pennies and the number of piles, for the sample that you checked? – Michael Lugo Aug 2 '13 at 19:01
@MichaelLugo Sorry, I threw away the source code and would have to rewrite it. – MJD Aug 2 '13 at 19:20

As you say, an even pile is a first player win, because that player can split it into matching piles and mirror the other player. The item about piles of 2 doesn't matter, as there will be duplicates of them. As the first player in this strategy, if my opponent can split a 2, there is always one for me to split.

A 3 pile is also a first player win, as you can split 2+1. 5 is second player, as you have to go to 3+2 or 4+1. 7 is second as 3+4 or 6+1 goes to 3+3+1 and 5+2 goes to 5+1+1.

-
If $7 \to 3+4$ then the move to $3+3+1$ gives a second player win – Mark Bennet Aug 1 '13 at 16:39
Note that I can play to lose an even stack, as well as playing to win it. I can lose $4\to 1+3$ and $6\to 2+4$ - but there is a lot of play in $6$ if I am trying to lose it in combination with other games, because if there are other piles in play, piles of $2$ can be split. – Mark Bennet Aug 1 '13 at 16:44
@MarkBennet: you are right. I corrected, and added the other choices. – Ross Millikan Aug 1 '13 at 16:53
oh, good catch! So the first player almost always wins? – narcissa Aug 1 '13 at 17:02
but for $9 \rightarrow 2 + 5 \rightarrow 1 + 1, 5$ means the first player loses.. – narcissa Aug 1 '13 at 17:04