HMMT 二月 2006 · COMB 赛 · 第 3 题

英文解析

3. A moth starts at vertex A of a certain cube and is trying to get to vertex B , which isopposite A , in five or fewer “steps,” where a step consists in traveling along an edgefrom one vertex to another. The moth will stop as soon as it reaches B . How manyways can the moth achieve its objective?
   Answer: 48
   Solution: Let X, Y, Z be the three directions in which the moth can intially go. Wecan symbolize the trajectory of the moth by a sequence of stuff from X s, Y s, and Z sin the obvious way: whenever the moth takes a step in a direction parallel or oppositeto X , we write down X , and so on.
   The moth can reach B in either exactly 3 or exactly 5 steps. A path of length 3 must be symbolized by XY Z in some order. There are 3! = 6 such orders. A trajectoryof length 5 must by symbolized by XY ZXX , XY ZY Y , or XY ZZZ , in some order,
   5!
   There are 3 · = 3 · 20 = 60 possibilities here. However, we must remember to
   3!1!1!
   subtract out those trajectories that already arrive at B by the 3 rd step: there are
   3 · 6 = 18 of those. The answer is thus 60 − 18 + 6 = 48. 1