Prove: In his winning strategy, player 1 (P1) in an $n \times n$ Chomp game must choose $(2,2)$
(See below for chomp description)
In an $n \times n$ Chomp game, we know that by choosing $(2,2)$, P1 secures his winning, because afterwards he could simply make symmetric moves to P2.
I'm trying to prove that $(2,2)$ must be the first move for P1 in order for him to win.
I've tried to proof by contradiction, but couldn't solve this. I've also tried by induction, but couldn't reduce the $n \times n$ board to a smaller squared board.
The Chomp game description, as was given here:
The game of Chomp is played by two players. In this game, cookies are laid out on a rectangular grid. The cookie in the top left position is poisoned. The two players take turns making moves; at each move, a player is required to eat a remaining cookie, together with all cookies to the right and/or below (that is all the remaining cookies in the rectangle, in which the first cookie eaten is the top left corner). The loser is the player who has no choice but to eat the poisoned cookie. Prove that if the board is square (and bigger than 1 × 1) then the first player has a winning strategy.
Best Answer
If the first player takes any other cookie that is not on the left or top edge, the second player can take the $(2,2)$ cookie and win. Suppose that the first player takes $(k,1)$ for some $k>1$. Then the game is essentially starting over on a $(k-1)\times n$ board, with the roles of the players reversed: player $2$ is the first player on this new board. But we know that the first player has a winning strategy on every rectangular board bigger than $1\times 1$. That means that the second player in the original game here can win by moving first on the $(k-1)\times n$ board, and this means that the first player’s move taking $(k,1)$ is a losing move. The situation with a $(1,k)$ move is of course symmetric.
The key here is that we don’t need to know how the second player can win by moving first on the $(k-1)\times n$ board: we just need to know that he has some winning move.