2010 AMC 10A Problem 20

P16-20~6 minPrint

Geometric Optimization Solid Geometry Bound the quantity above/below or estimate to pin it down Consider the largest/smallest element or boundary case

A fly trapped inside a cubical box with side length $1$ meter decides to relieve its boredom by visiting each corner of the box. It will begin and end in the same corner and visit each of the other corners exactly once. To get from a corner to any other corner, it will either fly or crawl in a straight line. What is the maximum possible length, in meters, of its path?

Show solution without answering

Key insight

Each corner touches only one longest jump, and the tour uses two jumps at every corner, so at most 4 of the 8 jumps are longest ones.

Solution

This is a "maximum possible" question, so it has two halves: show a path of that length exists, and show nothing can be longer.

What jumps are possible. Between two corners of a cube with side $1$ there are three kinds of straight lines:

Kind	Example	Length
Along an edge	one side of a face	$1$
Across a face (face diagonal)	corner to opposite corner of one face	$\sqrt2 \approx 1.41$
Through the middle of the cube (space diagonal)	corner to the opposite corner of the cube	$\sqrt3 \approx 1.73$

The fly visits $8$ corners and returns to the start, so its path has $8$ jumps.

Part 1: at most 4 space diagonals.

Each corner has exactly one opposite corner, so only one space diagonal touches it.
The fly arrives at each corner once and leaves once. That is two jumps touching that corner, and at most one of them can be the space diagonal.
Count the ends of space diagonals: each corner is the end of at most one used space diagonal, so there are at most $8$ ends. Each space diagonal has $2$ ends, so the path uses at most $8 \div 2 = 4$ of them.
The other $4$ jumps are at most face diagonals, $\sqrt2$ each. So the path is at most $4\sqrt3 + 4\sqrt2$ long.

Part 2: a path that reaches this length. Name each corner by three digits, each $0$ or $1$ (like coordinates). A space diagonal changes all three digits; a face diagonal changes exactly two. Alternate the two kinds:
$000 \to 111 \to 001 \to 110 \to 011 \to 100 \to 010 \to 101 \to 000.$
Every corner appears once, the jumps alternate space diagonal, face diagonal, and so on, and the fly ends where it started. Its length is $4\sqrt3 + 4\sqrt2$ .

The answer is $\boxed{\textbf{(D)}\ 4\sqrt{2}+4\sqrt{3}}$ .

Why this works

For a "maximum" question you need both an upper limit and an example that reaches it. The limit here comes from counting at each corner: one long jump available, two jumps used. Once you see that, the example is natural: after each longest jump, take the next-longest one.

Concise solution

A shorter write-up, the way contest solutions are usually written. It may take a different route from the solution above.

The path is a closed tour through the $8$ corners, so it has $8$ legs. A leg between two corners is an edge (length $1$ ), a face diagonal ( $\sqrt2$ ), or a space diagonal ( $\sqrt3$ ).

Upper bound. Each corner is the endpoint of exactly one space diagonal (the one to the opposite corner). The tour passes through each corner exactly once, using two legs there, so at most one of those two legs is a space diagonal. Counting each space diagonal at both of its endpoints, the tour contains at most $\dfrac{8}{2} = 4$ space diagonals. The remaining legs are at most $\sqrt2$ each, so the length is at most $4\sqrt3 + 4\sqrt2$ .

Construction. Label corners by coordinates. The tour
$000 \to 111 \to 001 \to 110 \to 011 \to 100 \to 010 \to 101 \to 000$
alternates: the odd legs flip all three coordinates (space diagonals) and the even legs flip exactly two (face diagonals). It visits every corner once and has length exactly $4\sqrt3 + 4\sqrt2$ .

The answer is $\boxed{\textbf{(D)}\ 4\sqrt{2}+4\sqrt{3}}$ .

Review in the AoPS books

Introduction to Geometry, Chapter 10: Geometric Inequalities
Introduction to Geometry, Chapter 14: Three-Dimensional Geometry
Introduction to Geometry, Chapter 15: Curved Surfaces