1957 AMC 12 Problem 17

Question

A cube is made by soldering twelve

3

-inch lengths of wire properly at the vertices of the cube. If a fly alights at one of the vertices and then walks along the edges, the greatest distance it could travel before coming to any vertex a second time, without retracing any distance, is:

24

in.

12

in.

30

in.

18

in.

36

in.

Answer: A

Concepts:cube geometry graph theory extremal argument

Difficulty rating: 1300

Small hint:

A path that never returns to a vertex can visit at most all eight cube vertices

Big hint:

Exhibit a path through all eight vertices, which uses seven edges before the next step returns to the starting vertex

Solution:

The cube has eight vertices. A path can visit all eight once, using seven edges, and then traverse the edge from its last vertex back to its starting vertex; the return is the first repeated vertex. Thus the greatest permitted walk uses eight edges. Its length is

8\cdot3=24

inches.

Therefore, the correct answer is A.