3 April, 19:28

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.)

0
1. 3 April, 20:16
0
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.