Chomp and the strategy-stealing argument

Idea. The game is finite and has no draws, so exactly one of the players has a winning strategy.

1. Strategy stealing. The first player considers the move $M$ that eats only the top-right corner square.
- If $M$ leads to a position that is losing for the opponent, the first player wins by playing $M$.
- Otherwise, the opponent has a winning reply $X$. The square chosen by $X$ was present at the start, and eating it together with everything above and to its right also removes the top-right corner square, so playing $X$ at the very start leads to the same position as $M$ followed by $X$. That position is losing for the player to move, so the first player wins by playing $X$ at once.

In both cases the first player has a winning strategy.

2. Two rows, explicit strategy. Let the top row have $t$ squares and the bottom row $b\ge t$. The first player starts by eating the top-right square, creating $t=n-1$, $b=n$. He keeps the invariant $b=t+1$ after each of his moves, until he reaches $t=0$, $b=1$, after which the opponent has to eat the poisoned square. Suppose the opponent faces $b=t+1$ and moves:
- he eats in the top row from column $c$: now $t'=c-1$ and $b=t+1\ge c+1$. The first player eats the bottom row from column $c+1$: the bottom row becomes $c$, restoring $b=t'+1$;
- he eats in the bottom row from column $c$ ($2\le c\le b$): the bottom row has $c-1$ squares and the top row has $c-1$ squares. The first player eats the end of the top row (column $c-1$, if $c\ge2$), leaving $t'=c-2$ and $b'=c-1$, so $b'=t'+1$ again.
The total number of squares decreases at each turn, so eventually the opponent is left with the poisoned square.

Remark. For rectangles with at least three rows and columns no explicit winning strategy is known in general.

Lesson. Strategy stealing proves existence; explicit strategies come from maintaining an invariant shape.