Maths Olympiad Prep

Library / /4 of 5

Geometry Difficulty 9.2 IMO level Prove it United States

There are 2022 equally spaced points on a circular track γ\gamma of circumference 2022. The points are labeled A1,A2,,A2022A_1, A_2, \dots, A_{2022} in some order, each label used once. Initially, Bunbun the Bunny begins at A1A_1. She hops along γ\gamma from A1A_1 to A2A_2, then from A2A_2 to A3A_3, until she reaches A2022A_{2022}, after which she hops back to A1A_1. When hopping from PP to QQ, she always hops along the shorter of the two arcs PQ\text{PQ} of γ\gamma; if PQ\text{PQ} is a diameter of γ\gamma, she moves along either semicircle.
Determine the maximal possible sum of the lengths of the 2022 arcs which Bunbun traveled, over all possible labellings of the 2022 points.

Solution

Replacing 2022 with 2n2n, the answer is 2n22n+22n^2 - 2n + 2.

Figure 1

Construction The construction for n=5n=5 shown on the left half of the figure easily generalizes for all nn.

First proof of bound Let did_i be the shorter distance from A2i1A_{2i-1} to A2i+1A_{2i+1}.

Claim — The distance of the leg of the journey A2i1A2iA2i+1A_{2i-1} \to A_{2i} \to A_{2i+1} is at most 2ndi2n - d_i.
Proof. Of the two arcs from A2i1A_{2i-1} to A2i+1A_{2i+1}, Bunbun will travel either did_i or 2ndi2n-d_i. One of those arcs contains A2iA_{2i} along the way. So we get a bound of max(di,2ndi)=2ndi\max(d_i, 2n-d_i) = 2n-d_i. \square

That means the total distance is at most
i=1n(2ndi)=2n2(d1+d2++dn). \sum_{i=1}^{n} (2n - d_i) = 2n^2 - (d_1 + d_2 + \dots + d_n).

Claim — We have
d1+d2++dn2n2. d_1 + d_2 + \dots + d_n \ge 2n - 2.
Proof. The left-hand side is the sum of the walk A1A3A2n1A1A_1 \to A_3 \to \dots \to A_{2n-1} \to A_1. Among the nn points here, two of them must have distance at least n1n-1 apart; the other did_i's contribute at least 1 each. So the bound is (n1)+(n1)1=2n2(n-1) + (n-1) \cdot 1 = 2n-2. \square

Second proof of bound Draw the nn diameters through the 2n2n arc midpoints, as shown on the right half of the figure for n=5n=5 in red.

Claim (Interpretation of distances) — The distance between any two points equals the number of diameters crossed to travel between the points.
Proof. Clear. \square

With this in mind, call a diameter critical if it is crossed by all 2n2n arcs.

Claim — At most one diameter is critical.
Proof. Suppose there were two critical diameters; these divide the circle into four arcs. Then all 2n2n arcs cross both diameters, and so travel between opposite arcs. But this means that points in two of the four arcs are never accessed — contradiction. \square

Claim — Every diameter is crossed an even number of times.
Proof. Clear: the diameter needs to be crossed an even number of times for the loop to return to its origin. \square
This immediately implies that the maximum possible total distance is achieved when one diameter is crossed all 2n2n times, and every other diameter is crossed 2n22n-2 times, for a total distance of at most
n(2n2)+2=2n22n+2. n \cdot (2n - 2) + 2 = 2n^2 - 2n + 2.

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.