Olympiad Maths Prep

Track / Stage 10 / 9 of 40 #1969 of 2000

Problem 1969

Hardest shortlist tier
Geometry Difficulty 9.2 Prove it USA TST · 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 \overarcPQ\overarc{PQ} of γ\gamma; if \overarcPQ\overarc{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.

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official 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.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.