There are some piles of stones.

Two players move in turn. One can remove a stone from a pile or merge two piles in a move. The player that removes the last stone wins.

With the number of stones in each pile given, how to know who will win?

  • $\begingroup$ In fact, I got a conclusion, but I don't know how to prove it. Suppose there are $p$ piles, $k$ piles that contain only one stone, and a total of $n$ stones. If $n \le p+1$, the first player lose when $k\bmod{3}=0$. If $n>p+1$ the first player lose when $p+n$ is odd and $k$ is even. $\endgroup$ – Tang Xianghao Jul 6 '13 at 12:31

Hint: Only by taking a pile which consists of a single stone can a player change the parity (see Brian's hint). Is there a strategy for a player who is winning on parity which avoids either player taking a single stone until the last move?

What happens when the initial position has a single pile of size 1?

What happens when there are several piles of size 1 in the initial position?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.