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?
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.