A rectangle of chocolate may seem like a calculation problem, but the right question is not how long the bar is: it is whether the first player can guarantee victory, and why.
The cursed chocolate
Riddle statement
A rectangular bar of chocolate is divided into squares, and the square in the upper left corner is poisoned. Two players take turns: on each turn, the player chooses a square and eats that square along with all the squares below and to the right of it.
The player who is forced to eat the poisoned square loses. If both play perfectly, who has a winning strategy?
Show solution
Solution
Answer: the first player has a winning strategy.
The demonstration does not always give us the specific move that the first player must make, but it does prove that a winning move exists.
First we observe that the game is finite: in each turn at least one square disappears. Also, there are no ties. Therefore, from any position, either the player whose turn it is can force victory, or he cannot.
Now the first player considers a minimum move: eating only the square in the lower right corner. That move is legal and does not touch the poisoned square.
There are two cases.
Case 1: after that move, the second player is in a losing position. Then the first player wins starting like this.
Case 2: after that move, the second player is in a winning position. Then the second has some response that leaves the first in a losing position.
But the second's response consists of choosing a square and eating everything that is below and to the right. That same choice was also legal from the initial board. Also, any such bite already includes the lower right corner, so directly doing that bite from the beginning produces the same result as:
- eat only the bottom right corner first;
- then make the second's winning response.
Therefore, if the second had a winning response after the minimum move, the first player could have made that same bite as the first move.
So, in either case, the first player has a winning move.
On a $2\times 2$ board, for example, removing the lower right corner does win directly. But on larger boards it is not necessary for this to always be the winning move: if it is not, the previous argument shows that there is another first winning move.