Question

Prove that the first player has a winning strategy for the game of Chomp, introduced in Example 12 in Section 1.8, if the initial board is square. [Hint: Use strong induction to show that this strategy works. For the first move, the first player chomps all cookies except those in the left and top edges. On subsequent moves, after the second player has chomped cookies on either the top or left edge, the first player chomps cookies in the same relative positions in the left or top edge, respectively.]

Short answer

It has been proved that the first player has a winning strategy for the game of Chomp, if the initial board is square.

Step-by-step solution

Describe the given information

Given that initial board of Chomp Game is square.

Let the board has n rows and n columns.

Prove using strong induction

Let $P\left(n\right)$: If a player has presented his opponent with a Chomp configuration consisting of just ncookies in the top row and ncookies in the left-most column then he can win the game.

The basis step:$P\left(1\right)$ is trivially true because the opposite player is forced to take the poisoned cookie at his first turn

Inductive hypothesis:$P\left(j\right)$ is true for all$j\le k$ and $k\ge 1$.

To show: The statement$P(k+1)$ is true.

Proof:It is the opponent's turn to move. If she picks the poisoned cookie, then the game is over

and she loses.

Otherwise, assume that she picks the cookie in the top row in column j,or the cookie in the

left column in row j,for some jwith $2\le j\le k+1$.

The first player now picks the cookie in the left column in row j,or the cookie in the top row in column j,respectively.

This leaves the position covered by$P(j-1)$ for his opponent, so by the inductive hypothesis, he can win.