Maths Olympiad Prep

Library / Harvard-MIT Mathematics Tournament /157 of 352

Harvard-MIT Mathematics Tournament

Combinatorics Difficulty 5.0 AIME, harder Find the answer United States

Problem:

There are thirteen broken computers situated at the following set SS of thirteen points in the plane:
A=(1,10)B=(976,9)C=(666,87)D=(377,422)E=(535,488)F=(775,488)G=(941,500)H=(225,583)I=(388,696)J=(3,713)K=(504,872)L=(560,934)M=(22,997) \begin{array}{lll} A=(1,10) & B=(976,9) & C=(666,87) \\ D=(377,422) & E=(535,488) & F=(775,488) \\ G=(941,500) & H=(225,583) & I=(388,696) \\ J=(3,713) & K=(504,872) & L=(560,934) \\ & M=(22,997) & \end{array}
At time t=0t=0, a repairman begins moving from one computer to the next, traveling continuously in straight lines at unit speed. Assuming the repairman begins at AA and fixes computers instantly, what path does he take to minimize the total downtime of the computers? List the points he visits in order. Your score will be ⌊N40⌋\left\lfloor\frac{N}{40}\right\rfloor, where
N=1000+⌊ the optimal downtime ⌋−⌊ your downtime ⌋, N=1000+\lfloor\text{ the optimal downtime }\rfloor-\lfloor\text{ your downtime }\rfloor,
or 00, whichever is greater. By total downtime we mean the sum
∑P∈StP \sum_{P \in S} t_{P}
where tPt_{P} is the time at which the repairman reaches PP.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:

Answer: ADHIKLEFGBCJM. This is an instance of the minimum-latency problem, which is at least NP-hard. There is an easy O(n!)O(n!) algorithm, but this is unavailable to teams on computational grounds (100 MHz calculators used to seem fast...) The best strategy may be drawing an accurate picture and exercising geometric intuition. The distribution of the points somewhat resembles a short, four-pronged fork with its outermost prongs bent apart; it is plausible to assume that the optimal order respects this shape. The optimal downtime is 24113.14790724113.147907, realized by ADHIKLEFGBCJM, though a number of others also receive positive marks.

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.