Question

一只虫子沿下图六角形网格中的线段从 $A$ 走到 $B$ 。带箭头标记的线段只能按箭头方向行走，并且这只虫子不会重复走同一条线段。有多少条不同路径？

A bug travels from $A$ to $B$ along the segments in the hexagonal lattice pictured below. The segments marked with an arrow can be traveled only in the direction of the arrow, and the bug never travels the same segment more than once. How many different paths are there?

$2112$

$2304$

$2368$

$2384$

$2400$

答案：E

知识点：分类讨论乘法原理

难度评级：2270

小提示：

有三条向左的“返回”线段；按路径使用了它们的哪个子集分类

There are three left-pointing “back” segments; split into cases by which subset of them the path uses

大提示：

若不使用返回线段，路径在每一列选择一条向前线段，共有 $2\cdot2\cdot4\cdot4\cdot4\cdot2\cdot2=2^{10}$ 条

With no back segment used, the path picks one forward segment per column, giving $2\cdot2\cdot4\cdot4\cdot4\cdot2\cdot2=2^{10}$

解答：

给七列向前（向右）线段编号；若路径不使用返回线段，它只是在每一列选择一条向前线段。选择数为 $2,2,4,4,4,2,2$ ，因此有 $2^{10}$ 条路径。

设 $s_1,s_2,s_3$ 为三条向左的返回线段（位于第 $2,4,6$ 列）。分析一旦走过一条返回线段，哪些列会被迫确定，可得：对 $\{s_1\}$ 和 $\{s_3\}$ ，各有 $2^8$ 条路径，对 $\{s_1,s_3\}$ 有 $2^6$ 条，对 $\{s_2\}$ 有 $2^9$ 条，对 $\{s_1,s_2\}$ 和 $\{s_2,s_3\}$ ，各有 $2^7$ 条，对 $\{s_1,s_2,s_3\}$ 有 $2^5$ 条。

相加得 $\begin{aligned} &2^{10}+2\cdot2^8+2^6 \\ &\quad {}+2^9+2\cdot2^7+2^5=2400 \end{aligned}\text{。}$

因此正确答案是 E。

Label the seven columns of forward (rightward) segments; a path with no back segment simply chooses one forward segment in each column. The numbers of choices are $2,2,4,4,4,2,2,$ giving $2^{10}$ paths.

Let $s_1,s_2,s_3$ be the three left-pointing back segments (in columns $2,4,6$ ). Analyzing which columns become forced once a back segment is traversed gives $2^8$ paths for each of $\{s_1\}$ and $\{s_3\},$ $2^6$ for $\{s_1,s_3\},$ $2^9$ for $\{s_2\},$ $2^7$ for each of $\{s_1,s_2\}$ and $\{s_2,s_3\},$ and $2^5$ for $\{s_1,s_2,s_3\}.$

Adding, $\begin{aligned} &2^{10}+2\cdot2^8+2^6 \\ &\quad {}+2^9+2\cdot2^7+2^5=2400. \end{aligned}$

Thus, the correct answer is E.

2012 AMC 12B 第 22 题

答案：E

难度评级：2270

小提示：

大提示：

解答：

其他年份的第 22 题