There are $2003$ pieces of candy on a table. Two players alternately make moves. A move consists of eating one candy or half of the candies on the table (the “lesser half” if there are an odd number of candies). At least one candy must be eaten at each move. The loser is the one who eats the last candy. Which player has a winning strategy?
Problem
Source: Baltic Way 2003
Tags: combinatorics unsolved, combinatorics, Game Theory
pythag011
11.11.2008 02:16
We prove that if there is an even number of candies, 2n, then the first player can win.
This is true for 2 candies. Assume it is true for 2(n-1) candies. We will prove it is true for 2n candies.
Assume that the first player can't win. Then, if he eats half of the candies, there will be n candies left. If he was losing, the position should now be a winning position for the second player.
Consider the possiblities when he takes one candy. The other person is left with 2n-1 candies. The other person can either take
a.)1 candy. Then the first player is left with a position with 2n-2 candies, which is winning by inductive hypothesis.
b.)half the candy. Then the first player is left with a position with n candies, which is winning.
Therefore, the first player wins.
Now, consider what happens if the first player has 2003 candies. If he eats one, the other person has 2002 candies, and the other person wins and the first player loses.
If he eats half of his candy, there are 1002 candies left, and the other person is winning, and the first player loses.
Therefore, the second player can win.
mavropnevma
05.08.2013 00:10
By retrograde analysis we can in fact decide who wins if starting with any $N>1$ candies. If we write $N=2^m i + 1$, with $i$ odd and $m\geq 0$, then the first player wins if $m$ is even, and the second player wins when $m$ is odd. This is because first player wins when $N$ is even, as shown above, and then because of the simple observation that $2^{m+1} i + 1$ is winning for a player if and only if $2^{m} i + 1$ is losing for that player (and of course, also the other way around). Now, since $2003 = 2^1\cdot 1001 + 1$, it agrees with the above analysis' conclusion that the second player wins. It would have been more challenging to ask, for example, for $N= 1537 = 2^9\cdot 3 + 1$.