Source

I got this problem from Rustan Leino, who was told it by Clark Barrett.

I solved it and wrote up my solution.

Problem

Given is a (possibly enormous) rectangular chocolate bar, divided into small squares in the usual way. The chocolate holds to 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 that, 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 $1 \times 1,$ 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.

Solution
Reveal

Suppose there's a rectangle for which the starting player doesn't have a winning strategy. Then, any move he makes must allow the non-starting player to win. In particular, the move of "eat only the upper-right square" must let the non-starting player win.

This means that, when presented with the rectangle with the upper-right square removed, the non-starting player has some winning strategy. In particular, there is some square $S$ he can point to that will let him win. After he eats that square and every square above and/or to the right of it, the chocolate bar will be in some state $C$ from which the next player to go (the starting player) cannot win.

Now, imagine that, at the beginning of the game, the starting player had pointed to square $S$ instead of the upper-right corner. He would leave the chocolate bar in state $C,$ which we know is a losing position for the next player to go, in this case the non-starting player. In other words, the starting player will win! This contradiction shows that our earlier supposition was false. In other words, there is no rectangle for which the starting player doesn't have a winning strategy.