Maths Olympiad Prep

Library / /262 of 377

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:

A moth starts at vertex AA of a certain cube and is trying to get to vertex BB, which is opposite AA, 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 BB. How many ways can the moth achieve its objective?

Solution

Solution:

Let XX, YY, ZZ be the three directions in which the moth can initially go. We can symbolize the trajectory of the moth by a sequence of XX's, YY's, and ZZ's in the obvious way: whenever the moth takes a step in a direction parallel or opposite to XX, we write down XX, and so on.

The moth can reach BB in either exactly 33 or exactly 55 steps. A path of length 33 must be symbolized by XYZX Y Z in some order. There are 3!=63! = 6 such orders.

A trajectory of length 55 must be symbolized by XYZXXX Y Z X X, XYZYYX Y Z Y Y, or XYZZZX Y Z Z Z, in some order. There are 35!3!1!1!=320=603 \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 BB by the 33rd step: there are 36=183 \cdot 6 = 18 of those.

The answer is thus 6018+6=4860 - 18 + 6 = 48.

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

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