2010 AMC 10A Problem 20

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:

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

Part 1: at most 4 space diagonals.

1. Each corner has exactly one opposite corner, so only one space diagonal touches it.
2. 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.
3. 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.
4. 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}}$.

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.

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}}$.