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?
一只虫子沿着下图所示的六边形格点从 A 到 B 移动。标有箭头的线段只能沿箭头方向行进,且虫子永不重复行进同一条线段。有多少条不同的路径?
Answer (E):
Label the columns having arrows as $c_1, c_2, c_3, \ldots, c_7$ according to the figure. Call those segments that can be traveled only from left to right forward segments. Call the segments $s_1$, $s_2$, and $s_3$, in columns $c_2$, $c_4$, and $c_6$, respectively, which can be traveled only from right to left, back segments. Denote $S$ as the set of back segments traveled for a path.
First suppose that $S=\emptyset$. Because it is not possible to travel a segment more than once, it follows that the path is uniquely determined by choosing one forward segment in each of the columns $c_j$. There are $2, 2, 4, 4, 4, 2,$ and $2$ choices for the forward segment in columns $c_1, c_2, c_3, c_4, c_5, c_6,$ and $c_7$, respectively. This gives a total of $2^{10}$ total paths in this case.
Next suppose that $S=\{s_1\}$. The two forward segments in $c_2$, together with $s_1$, need to be part of the path, and once the forward segment from $c_1$ is chosen, the order in which the segments of $c_2$ are traveled is determined. Moreover, there are only $2$ choices for possible segments in $c_3$ depending on the last segment traveled in $c_2$, either the bottom $2$ or the top $2$. For the rest of the columns, the path is determined by choosing any forward segment. Thus the total number of paths in this case is $2\cdot 1\cdot 2\cdot 4\cdot 4\cdot 2\cdot 2=2^8$, and by symmetry this is also the total for the number of paths when $S=\{s_3\}$. A similar argument gives $2\cdot 1\cdot 2\cdot 4\cdot 2\cdot 1\cdot 2=2^6$ trips for the case when $S=\{s_1,s_3\}$.
Suppose $S=\{s_2\}$. Because $s_2$ is traveled, it follows that $2$ forward segments in $c_4$ need to belong to the path, one of them above $s_2$ ($2$ choices) and the other below it ($2$ choices). Once these are determined, there are $2$ possible choices for the order in which these segments are traveled: the bottom forward segment first, then $s_2$, then the top forward segment, or vice versa. Next, there are only $2$ possible forward segments that can be selected in $c_3$ and also only $2$ possible forward segments that can be selected in $c_5$. The forward segments in $c_1, c_2, c_6,$ and $c_7$ can be freely selected ($2$ choices each). This gives a total of $(2^3\cdot 2\cdot 2)\cdot 2^4=2^9$ paths.
If $S=\{s_1,s_2\}$, then the analysis is similar, except for the last step, where the forward segments of $c_1$ and $c_2$ are determined by the previous choices. Thus there are $(2^3\cdot 2\cdot 2)\cdot 2^2=2^7$ possibilities, and by symmetry the same number when $S=\{s_2,s_3\}$.
Finally, if $S=\{s_1,s_2,s_3\}$, then in the last step, all forward segments of $c_1, c_2, c_6,$ and $c_7$ are determined by the previous choices and hence there are $2^3\cdot 2\cdot 2=2^5$ possible paths. Altogether the total number of paths is $2^{10}+2\cdot 2^8+2^6+2^9+2\cdot 2^7+2^5=2400$.
答案(E):
按照图示,把带箭头的列标记为 $c_1, c_2, c_3, \ldots, c_7$。把只能从左到右行走的线段称为“前向线段”。把分别位于 $c_2, c_4, c_6$ 三列且只能从右到左行走的线段 $s_1, s_2, s_3$ 称为“后向线段”。用 $S$ 表示一条路径中所经过的后向线段集合。
先设 $S=\emptyset$。因为一条线段不可能被走超过一次,所以路径由在每一列 $c_j$ 中选择一条前向线段唯一确定。各列 $c_1, c_2, c_3, c_4, c_5, c_6, c_7$ 的前向线段选择数分别为 $2, 2, 4, 4, 4, 2, 2$。因此此情形下共有 $2^{10}$ 条路径。
再设 $S=\{s_1\}$。$c_2$ 中的两条前向线段与 $s_1$ 必须属于该路径;并且一旦选定 $c_1$ 的前向线段,走完 $c_2$ 中各线段的顺序就确定了。此外,$c_3$ 中可选的线段只有 $2$ 种,取决于在 $c_2$ 中最后经过的是下面两条还是上面两条。其余各列只需任选一条前向线段即可确定路径。因此该情形下路径总数为 $2\cdot 1\cdot 2\cdot 4\cdot 4\cdot 2\cdot 2=2^8$;由对称性,当 $S=\{s_3\}$ 时总数也为 $2^8$。同理可得当 $S=\{s_1,s_3\}$ 时共有 $2\cdot 1\cdot 2\cdot 4\cdot 2\cdot 1\cdot 2=2^6$ 次行走(路径)。
设 $S=\{s_2\}$。由于经过了 $s_2$,则 $c_4$ 中必须有两条前向线段属于路径:一条在 $s_2$ 之上($2$ 种选择),另一条在其之下($2$ 种选择)。一旦它们确定,行走顺序还有 $2$ 种:先走下面的前向线段,再走 $s_2$,再走上面的前向线段;或反过来。接着,在 $c_3$ 中只有 $2$ 条可选前向线段,在 $c_5$ 中也只有 $2$ 条可选前向线段。$c_1, c_2, c_6, c_7$ 中的前向线段可自由选择(每列 $2$ 种)。因此共有 $(2^3\cdot 2\cdot 2)\cdot 2^4=2^9$ 条路径。
若 $S=\{s_1,s_2\}$,分析类似,但最后一步中,$c_1$ 与 $c_2$ 的前向线段由之前的选择决定。因此共有 $(2^3\cdot 2\cdot 2)\cdot 2^2=2^7$ 种可能;由对称性,当 $S=\{s_2,s_3\}$ 时也同样为 $2^7$。
最后,若 $S=\{s_1,s_2,s_3\}$,则在最后一步中,$c_1, c_2, c_6, c_7$ 的所有前向线段都由先前选择决定,因此共有 $2^3\cdot 2\cdot 2=2^5$ 条可能路径。总路径数为
$2^{10}+2\cdot 2^8+2^6+2^9+2\cdot 2^7+2^5=2400$。