Maths Olympiad Prep

Library / /171 of 377

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
PStP \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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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