3
$\begingroup$

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?

$\endgroup$
1
  • $\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$ Jul 6, 2013 at 12:31

1 Answer 1

1
$\begingroup$

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?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .