HMMT 二月 2006 · COMB 赛 · 第 3 题

HMMT February 2006 — COMB Round — Problem 3

A moth starts at vertex A of a certain cube and is trying to get to vertex B , which is opposite A , in five or fewer “steps,” where a step consists in traveling along an edge from one vertex to another. The moth will stop as soon as it reaches B . How many ways can the moth achieve its objective?

解析

A moth starts at vertex A of a certain cube and is trying to get to vertex B , which is opposite A , in five or fewer “steps,” where a step consists in traveling along an edge from one vertex to another. The moth will stop as soon as it reaches B . How many ways can the moth achieve its objective? Answer: 48 Solution: Let X, Y, Z be the three directions in which the moth can intially go. We can symbolize the trajectory of the moth by a sequence of stuff from X s, Y s, and Z s in the obvious way: whenever the moth takes a step in a direction parallel or opposite to 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 trajectory of 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 3rd step: there are 3 · 6 = 18 of those. The answer is thus 60 − 18 + 6 = 48. 1