Library / Harvard-MIT Mathematics Tournament /105 of 352

Harvard-MIT Mathematics Tournament

Geometry Difficulty 4.9 AIME Find the answer United States

Problem:

$\begin{array}{rlrr} A=(0,428) & B=(9,85) & C=(42,865) & D=(192,875) \\ E=(193,219) & F=(204,108) & G=(292,219) & H=(316,378) \\ I=(375,688) & J=(597,498) & K=(679,766) & L=(739,641) \\ & M=(772,307) & & N=(793,0) \\ & \end{array}$
A fly starts at $A$ , visits all the other points, and comes back to $A$ in such a way as to minimize the total distance covered. What path did the fly take? Give the names of the points it visits in order. Your score will be
$20+\lfloor\text{ the optimal distance }\rfloor-\lfloor\text{ your distance }\rfloor$
or $0$ , whichever is greater.

Solution

Solution:

This problem is an instance of the Traveling Salesman Problem, which is NP-hard. There is an obvious algorithm in $O(n!)$ time (where $n$ is the number of points), but faster algorithms exist. Nonetheless, the best strategy for solving this problem is probably to draw the points and exercise your geometric intuition.

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

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