Find a winning strategy in a stone game.

Question

Alice and Bob play the following game: There are piles of stones and in each turn the player can do one of the following: Remove one stone from a pile, or take two piles with $x$ and $y$ stones in them and replace them with $1$ pile of $xy$ stones. The player who has no move loses. Who has the winning strategy?

The answer can depend on the number of piles and the number of stones in each pile. I think I got an extremely ugly inductive solution. What I got is that the first player wins if and only if there is an odd number of stones, or there is an even number of stones and a positive even amount of piles with even amount of stones in them. I might be mistaken somewhere though. Does anyone have something elegant?

Answer 1

A situation consists of $e$ even-sized and $o$ odd-sized non-empty heaps. I claim that winning or losing depends only on $(e,o)$. Let $W$ be the set of positions $(e,o)$ that are winning and $L$ the set of $(e,o)$ that are losing positions.

Claim. We have $$W=\{\,(e,o)\mid o\text{ odd}\lor(e\text{ even}\land e\ne 0)\,\}$$ and $$L=\{\,(e,o)\mid o\text{ even}\land (e\text{ odd}\lor e=0)\,\}.$$

Proof. Since the game must end after finitely many moves, it ssuffices to show that every valid move from a situation $\in L$ leads to a situation $\in W$, and at for every situation $\in W$, there exists a valid move to a situation $\in L$.

Let us start with $(e,o)\in L$:

First case: $o$ is even and $e=0$. Removing a stone from any (necessarily odd) heap decreases $o$ to an odd number, hence takes us to $W$. Combining two (necessarily odd) heaps also decreases $o$ by one, hence takes us to $W$. We conclude that $(o,0)\in L$ for odd $o$.

Second case: $o$ is even and $e$ odd. Removing a stone from an odd heap or combining two odd heaps or combining an odd and an even heap, decreases $o$ to odd, hence takes us to $W$ Removing a stone from an even heap increases $o$ to odd, hence takes us to $W$. Finally, combining two even heaps (which is possible only if $e\ge 3$) takes us to $(e',o')=(e-1,o')$ with $e'$ even and positive, so again to $W$.

So indeed every valid move from a situation $\in L$ takes us to a situation $\in W$.

Next consider $(e,o)\in W$:

First case: $e$ is even and positive. If $o$ is even, we can combine two even heaps to arrive at $(e',o')=(e-1,o)\in L$. If $o$ is odd, we can remove a stone from one of the even heaps and arrive at $(e',o')=(e-1,o+1)\in L$.

Second case: $o$ is odd and $e=0$. By removing a stone from an odd heap, we arrive at either $(e',o')=(1,o-1)\in L$ or (if we emptied a heap) $(e',o')=(0,o-1)\in L$.

Third case: $o$ is odd and $e$ is odd. Combine an odd and an even heap to arrive at $(e',o')=(e,o-1)\in L$.

These cases logically cover all of $W$. So indeed, from every situation in $W$, there exists a valid move to $L$. $\square$