1. ## N candies

Two polite but vindictive children play a game as follows. They start with a bowl of N candies, the number known to both contestants. In turn, each child takes (if possible) one or more candies, subject to the rule that no child may take, on any one turn, more than half of what is left. The winner is not the child who gets the most candy, but the last child who gets to take some. Thus, if there are 3 candies, the first player may only take one, as two would be more than half. The second player may take one of the remaining candies; and the first player cannot move and loses.

(a) Show that if the game begins with 2000 candies the first player wins.

(b) Show that if the game begins with 999...999 (2000 9's) candies, the first player wins.

2. ## The Candy Game

*pretty long musing ahead* The 1st player must force the 2nd player to be left with 1 candy at the end of the game in order to win.

Working backwards... The 1st player can be left with 2 candies.

2 = 1 + maximum number of candies that can be taken = 1 + 1 = 2 * 1 = 2

(the addition of maximum number of candies that can be taken gives the 1st player much liberty, so just double the number of candies)

If k is the number of candies left in the pile, the 2nd player can take anywhere between 1 to k/2, inclusive. The 1st player must take care that, whatever happens, 1st player will be left with 2 candies.

Hence, the 2nd player must be left with 3 candies. That is: 2 + minimum number of candies that can be taken = 2 + 1

That way, whether 2nd player decides to take 1 candy, or k/2 candies, or any number of candies in between, the 1st player will be left with a number of candies which he can manipulate to eventually leave poor 2nd player with 1 candy at the end.

It's that one candy that will eventually bring about the 2nd player's demise.

*end of musing*

So, working backwards:

2nd player is left with 1 candy.
1st player is left with 2 (1) = 2 candies
2nd player is left with 2 (1) + 1 = 3 candies
1st player is left with 2 ( 2 (1) + 1 ) = 2^2 + 2 candies
2nd player left with (2^2 + 2) + 1 candies
1st player left with 2 (2^2 + 2 + 1) = 2^3 + 2^2 + 2 candies
2nd player left with 2^3 + 2^2 + 2 + 1 candies

and so on...

So in order to force the 2nd player to lose, he must be left with this number of candies:

$\displaystyle 2^{n-1} + 2^{n-2} + ... 2 + 1 = 2^n - 1$

which the 1st player can happily induce the 2nd player to have, given an initial 2000 candies.

All that the 1st player has to do is to leave the 2nd player with 1023 candies, and it's downhill for the 2nd player from then on.

3. ## With regards to item B

The first player always has the advantage in this game. As long as he doesn't have the (rare) misfortune of beginning the game with 2^n - 1 candies, and he knows that he has to get the candies down to 2^n - 1, he is guaranteed not to lose.

999...999 definitely is not a 2^n - 1 number, since no 2^n ends with a zero. Hence, player 1 wins.