CHOMP

How to play Chomp:

Chomp is played on a rectangular grid, such as squares of a candy bar. The lower left square is considered “poison”. Players take turns picking a square. With each choice, all squares above and to the right of the picked square are no longer available – they are eaten. The person forced to take the “poison” square loses.

Example: Playing on a 3x8 grid, the lower left square (in black) is the poison square. The first player chooses the red square of the grid and all the blue squares are eaten.

Then the second player chooses the yellow square:

The first player responds with the red square:

The second player plays the yellow square:

The first player plays the red square:

Now the second player must choose the black poison square and loses.

Use a piece of graph paper and try playing some games on a variety of sizes of boards. Below are a few questions to help you think about strategies to win.

(1) Who has a winning strategy? Is either player able to control the game? If so, which player can assure he/she wins?

HINT: Suppose there is a winning strategy. Is the first player following a winning strategy by picking the upper right square?

ANSWER: If there is a winning strategy, then either the upper right square is a move that will continue to allow the first player a winning strategy or it isn’t. If it is the first player has a winning strategy. If it isn’t, the second person must then have a move they can make as part of their winning strategy. But since this move would also eat up the upper right square, the first player could have made the same move with the same results - winning! Therefore the first player has the winning strategy. This proof was first given by David Gale. Unfortunately, it can be much harder to FIND the winning strategy!

The fact that there IS a winning strategy is a result of the fact that since the game is finite and that someone has to win!

(2) Winning on a square board: Consider square boards (3x3, 4x4, 5x5, …) Can you find any positions from which you can guarantee you can win?

HINT: Consider how you can use symmetry!You might also ask students which symmetries the board WITH the poison square has!

ANSWER: Consider the move above and to the right of the poison square. Then you are left with the poison square and two identical strips, one above the poison square and the other to the right. Wherever the other player moves, make a move to keep symmetry. For example, if the other player takes the blue square, then take the red square.

Because of the symmetry, you will always have a move to make that doesn’t involve taking the poison square. Therefore your opponent must eventually take the poison square and you win!

(3) Winning on a 2xn board: Consider boards with 2 rows (2x3,2x4, 2x5,…) Can you find any positions from which you can guarantee you can win? How can you make sure that you can get to those positions?

HINT: For the last question, you could win with symmetry. How can you get symmetry here? What do you have to do to guarantee that you’ll get to that position?

ANSWER: In order to get symmetry, we have to get to the point where only the poison square is left or there is one square open above the poison and one to the right, as below:

In order to get there, we need to maintain having one more square shaded in the top row than in the bottom row. Therefore, if the other player plays in the top row (red) you play in the bottom row (blue) (Figure 1) and if the other player plays in the bottom row (red), you play in the top row (blue) (Figure 2)

Figure 1:Figure 2:

So as the first player, with a winning strategy, your first move should be to take the upper right corner so that you set up this pattern.

----

Note: The 3xn case was solved in 2002 as part of a larger theorem by a high school senior who won the Westinghouse Science prize. This illustrates how a simple problem can be unsolved for quite some time – and yet be tackled by a bright high school student!