Question

下图显示了一个宽 $8$ 格、高 $3$ 格的点阵网格，由 $1''\times1''$ 的正方形组成。Carl 沿某些正方形边放置 $1$ 英寸长的牙签，形成一条不自交的闭合回路。格子中的数字表示该正方形有多少条边必须被牙签覆盖；没有写数字的格子允许任意数量的牙签。Carl 有多少种放置牙签的方法？

A dotted grid 8 cells wide and 3 cells tall, with a 1 written in each cell of the middle row.

The figure below shows a dotted grid $8$ cells wide and $3$ cells tall consisting of $1''\times1''$ squares. Carl places $1$ -inch toothpicks along some of the sides of the squares to create a closed loop that does not intersect itself. The numbers in the cells indicate the number of sides of that square that are to be covered by toothpicks, and any number of toothpicks are allowed if no number is written. In how many ways can Carl place the toothpicks?

A dotted grid 8 cells wide and 3 cells tall, with a 1 written in each cell of the middle row.

$130$

$144$

$146$

$162$

$196$

答案：C

知识点：图论分类讨论

难度评级：2370

小提示：

中间一行的每个格子必须恰好接触一根牙签；两端的折返列一旦固定，每个内部格子的牙签就独立地位于它的上边或下边

Each middle-row cell must touch exactly one toothpick; after the two turnaround columns are fixed, each interior cell’s toothpick is independently above or below it

大提示：

穿过中间带的回路会用到全部 $8$ 列、前 $7$ 列、后 $7$ 列或中间 $6$ 列；它的内部各列独立地向上或向下弯折

A loop crossing the middle uses all $8,$ the first $7,$ the last $7,$ or the middle $6$ columns; its interior columns independently bend above or below

解答：

中间一行的每个格子必须恰好接触一根牙签。先考虑从中间带的一侧穿到另一侧的回路。回路可以横跨全部 $8$ 列、前 $7$ 列、后 $7$ 列或中间 $6$ 列；更窄的跨度会使外侧某个中间格没有牙签。

一旦两端固定，每个内部中间格可以独立选择让其唯一牙签位于上边或下边，其余不自交回路都被迫确定。因此四种情形分别贡献 $2^6,2^5,2^5$ ，和 $2^4$ 条回路。另外，恰有两条回路不穿过中间带：完全沿顶部或完全沿底部的水平长方形。因此总数为 $2^6+2^5+2^5+2^4+2$ $=64+32+32+16+2$ $=146$ 。

因此，正确答案是 C。

Each middle-row cell must touch exactly one toothpick. First consider loops that pass from one side of the middle strip to the other. The loop can span all $8$ columns, the first $7,$ the last $7,$ or the middle $6;$ a narrower span would leave an outer middle cell untouched.

Once the two ends are fixed, each interior middle cell independently has its one toothpick on its top or bottom side, and the rest of the non-self-intersecting loop is forced. The four cases therefore contribute $2^6,2^5,2^5,$ and $2^4$ loops. There are also exactly two loops that do not cross the middle strip: the horizontal rectangle running entirely along the top or entirely along the bottom. Hence the total is $2^6+2^5+2^5+2^4+2$ $=64+32+32+16+2$ $=146.$

Thus, the correct answer is C.

2024 AMC 12A 第 22 题

答案：C

难度评级：2370

小提示：

大提示：

解答：

其他年份的第 22 题