2020 AMC 10A Problem 19
As shown in the figure below, a regular dodecahedron (the polyhedron consisting of congruent regular pentagonal faces) floats in empty space with two horizontal faces. Note that there is a ring of five slanted faces adjacent to the top face, and a ring of five slanted faces adjacent to the bottom face. How many ways are there to move from the top face to the bottom face via a sequence of adjacent faces so that each face is visited at most once and moves are not permitted from the bottom ring to the top ring? 
Show solution without answering
Key insight
Every route goes: top face, along the top ring, down, along the bottom ring, bottom face. Each ring walk has 9 options, so 5 times 9 times 2 times 9.
Solution
First understand which faces touch which. Each face in the top ring touches the top face, its two neighbors in the ring, and two faces of the bottom ring. The bottom ring is the same, flipped over.
A route cannot go back to the top face (no repeats), and it cannot climb from the bottom ring to the top ring. So every route looks like this:
top face some faces of the top ring some faces of the bottom ring bottom face.
Count each stage.
1. Enter the top ring. Any of its faces: ways.
2. Walk along the top ring. Label the ring faces in a circle and say you entered at face . You may:
- stop right away at face : way;
- go clockwise , , or steps: ways;
- go counterclockwise , , or steps: ways.
You cannot turn back, because that would repeat a face. So there are ways, and each one ends at a definite face.
3. Step down. The face where you stopped touches faces of the bottom ring: ways.
4. Walk along the bottom ring. Same reasoning as step 2: ways.
5. Step onto the bottom face. Every bottom-ring face touches it: way.
Multiply the stages:
The answer is .
Why this works
The rule against going back up forces every route to pass through the layers in order. Then the choices at each stage do not depend on earlier choices (only on where you are), so the total is a product. On a ring of faces, a walk that never repeats a face can stop immediately or go to steps in either direction, which gives walks.
Concise solution
A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.
Each face of the top ring touches the top face, its two ring neighbors, and two faces of the bottom ring (its remaining two edges). Likewise each bottom-ring face touches the bottom face, two ring neighbors, and two top-ring faces.
Since a route cannot return to the top face and cannot climb from the bottom ring back to the top ring, every route has the shape: top face, some faces of the top ring, some faces of the bottom ring, bottom face.
Stage 1: choose the first top-ring face: ways.
Stage 2: wander along the top ring without repeating. The ring is a -cycle, so from the entry face you can stop immediately ( way) or move or steps clockwise or counterclockwise ( ways): ways in all, each ending at a definite face.
Stage 3: from the final top-ring face, step down to one of its adjacent bottom-ring faces: ways.
Stage 4: wander along the bottom ring: again ways.
Stage 5: step onto the bottom face: way.
Total: .
The answer is .
Review in the AoPS books
- Introduction to Counting & Probability, Chapter 1: Counting Is Arithmetic
- Introduction to Counting & Probability, Chapter 5: More With Combinations (§5.2)
- Introduction to Geometry, Chapter 14: Three-Dimensional Geometry
- Introduction to Algebra, Chapter 22: Special Manipulations (§22.3)
Similar problems
Problem © Mathematical Association of America (MAA), American Mathematics Competitions. Reproduced for non-commercial educational use. Solution and commentary are original to this site.