Question

在 Chomp 游戏中，两名玩家轮流从一个由单位正方形组成的 $5$ 乘 $7$ 方格中“咬”下一块。每次行动时，玩家选择一个尚未被移除的方格，然后移除（“吃掉”）由该方格左边向上延长、下边向右延长所确定象限内的所有方格。例如，图中阴影方格所确定的一次行动会移除该阴影方格以及标有 $\times$ 的四个方格。（具有两条或更多虚线边的方格已经在先前的行动中从原棋盘上移除。）

游戏的目标是迫使对手进行最后一次行动。图中所示的是这 $35$ 个单位方格的众多可能子集之一。Chomp 游戏中一共可能出现多少个不同的子集？计数时包括完整棋盘和空棋盘。

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.

答案

答案：792

知识点：格路组合子集

难度评级：2320

小提示：

一个可出现的方格集合由介于 $0$ 与 $5$ 之间的非递增列高唯一确定

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

大提示：

将这种集合的边界编码为含 $5$ 个竖直步和 $7$ 个水平步的格路径

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

解答：

经过任意一系列行动后，剩余方格都构成一个左下闭集：七列的高度是介于 $0$ 与 $5$ 之间的非递增整数。反过来，每条这样的边界都可以出现，并对应于穿过一个 $5$ 乘 $7$ 矩形的格路径。每条路径由 $5$ 个竖直步和 $7$ 个水平步组成，所以包括完整棋盘和空棋盘在内，状态总数为 $\binom{12}{5}=792\text{。}$

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 第 12 题

答案：792

难度评级：2320

小提示：

大提示：

解答：

其他年份的第 12 题