Two polite but vindictive children play a game as follows. They start with a bowl ofNcandies, 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.