Question

Prove that the first player has a winning strategy in the game of Chomp if the initial board is two squares wide, that is, a 2 × n board. (See textbook for hint and for explanation of the game of Chomp.)

Answer 1

Explanation:

We can demostrate this claim by using global induction.

First, if the board has only one row, then you eat the non poissoned block and you win.

If it is a 2x2 row, then you have to eat the bottom right block, and in his next move, your opponent will be forced to eat only one block, leaving only 2 on the table. Then you eat the non poissoned one and you win.

Lets suppose that you have a winning strategy for a 2xk board, for k < n. If the board has dimensions 2xn, then

• You eat the bottom right corner block
• If your opponent eats exactly the block next to it, then you apply the winning strategy and its done.
• If your opponent eats a right-side block, then you can always eat the left-side block immediately below to it, leaving the board in a similar state than after your first move. Then you keep applying the same strategy until your opponent cant eat right side blocks.
• If your opponent instead eats a left side block, then the board will turn into a 2xj board and you can use a winning strategy (which exists due to the inductive hypothesis).

This way, you will always have a winning strategy by being first.