Question

In a game of Chomp, two players alternately take bites from a $5$ -by- $7$ grid of unit squares. To take a bite, a player chooses one of the remaining squares, then removes (“eats”) all squares in the quadrant defined by the left edge (extended upward) and the lower edge (extended rightward) of the chosen square. For example, the bite determined by the shaded square in the diagram would remove the shaded square and the four squares marked by $\times.$ (The squares with two or more dotted edges have been removed from the original board in previous moves.)

The object of the game is to make one’s opponent take the last bite. The diagram shows one of the many subsets of the set of $35$ unit squares that can occur during the game of Chomp. How many different subsets are there in all? Include the full board and empty board in your count.

Answer

Answer: 792

Concepts:lattice paths combinations subsets

Difficulty rating: 2320

Small Hint:

A reachable set is determined by nonincreasing column heights between $0$ and $5$

Big Hint:

Encode the boundary of such a set as a lattice path with $5$ vertical and $7$ horizontal steps

Solution:

After any sequence of bites, the remaining squares form a lower-left order ideal: the seven column heights are nonincreasing integers between $0$ and $5.$ Conversely, every such boundary can be produced and corresponds to a lattice path across a $5$ -by- $7$ rectangle. Each path consists of $5$ vertical and $7$ horizontal steps, so the number of states, including full and empty, is $\binom{12}{5}=792.$

1992 AIME Problem 12

Answer: 792

Difficulty rating: 2320

Small Hint:

Big Hint:

Solution:

Problem 12 in Other Years