[Clark Barrett told me this problem.]

Given is a (possibly enormous) rectangular chocolate bar, divided into small squares in the usual way. The chocolate holds a high quality standard, except for the square in the lower left-hand corner, which is poisonous. Two players take turns eating from the chocolate in the following manner: The player whose turn it is points to any one of the remaining squares, and then eats the selected square and all squares positioned above the selected square, to the right of the selected square, or both above and to the right of the selected square. Note, although the board starts off rectangular, it may take on non-rectangular shapes during game play. The object of the game is to avoid the poisonous square. Assuming the initial chocolate bar is larger than 1x1, prove that the player who starts has a winning strategy.

Hint: To my knowledge, no efficient strategy for winning the game is known. That is, to decide on the best next move, a player may need to consider all possible continuations of the game. Thus, you probably want to find a non-constructive proof. That is, to prove that the player who starts has a winning strategy, prove just the existence of such a strategy; in particular, steer away from proofs that would construct a winning strategy for the initial player.

March 2010