Library / Harvard-MIT Mathematics Tournament /242 of 352

Harvard-MIT Mathematics Tournament

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:

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?

Solution

Solution:

Let $X$ , $Y$ , $Z$ be the three directions in which the moth can initially go. We can symbolize the trajectory of the moth by a sequence of $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 $X Y Z$ in some order. There are $3! = 6$ such orders.

A trajectory of length $5$ must be symbolized by $X Y Z X X$ , $X Y Z Y Y$ , or $X Y Z Z Z$ , in some order. There are $3 \cdot \frac{5!}{3!1!1!} = 3 \cdot 20 = 60$ possibilities here. However, we must remember to subtract out those trajectories that already arrive at $B$ by the $3$ rd step: there are $3 \cdot 6 = 18$ of those.

The answer is thus $60 - 18 + 6 = 48$ .

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.