Maths Olympiad Prep

Library / /73 of 87

Geometry Difficulty 7.2 National Olympiad, round 2 Prove it Serbia

On a spherically shaped planet XX there are 2n2n gas stations. Each station is paired with exactly one other station, and any two paired stations are located at diametrically opposite points of the planet. Each station has a certain amount of gasoline available. The following is known: if a car with a previously empty (sufficiently large) tank starts from any station, it can always reach the station paired with it (possibly refueling at other stations along the way). Determine all natural numbers nn such that, for any arrangement of 2n2n stations satisfying the above condition, there always exists a station from which a car can start with a previously empty tank and visit all the other stations on the planet. (Assume that the car consumes a constant amount of gasoline per unit of distance.) (Nikola Petrović)

Solution

Solution:

The answer is n3n \leqslant 3.
The station diametrically opposite to station XX will be denoted by XX'.

For n1n \leqslant 1 the claim is trivial. Let n=2n=2 and let AB=ABAB=A'B' be the smallest among all distances between two stations. From station AA one can reach AA', say via the path ABAAB'A' (the case of the path ABAABA' is similar), but at BB there is enough gasoline to drive to the station nearest to it, which is AA, so the route BABABAB'A' is possible.

Let us prove the claim for n=3n=3 and six stations A,A,B,B,C,CA, A', B, B', C, C'. Let AB=ABAB=A'B' be the smallest among the distances between two stations, and let BB be the station nearest to CC. Denote S={A,B,C}S=\{A, B, C\} and S={A,B,C}S'=\{A', B', C'\}. Starting from any station of one set, one can reach the other set.

(1) Suppose that from station AA via the path ABAB one cannot reach the set SS'. One also cannot reach SS' via ACAC - otherwise it would also be possible via ABCABC, since BCACBC \leqslant AC, and at BB there is enough gasoline to make up for the consumption on the path ABAB. Hence, starting from station AA, one can reach SS' only directly. The nearest point of the set SS' is CC', so the entire route CBACBACBA C'B'A' is possible. The case when from AA' via the path ABA'B' one cannot reach SS is analogous.

(2) If case (1) does not hold, let us start from AA straight to BB. Since the set SS' is within reach, and BCd(B,S)=BCBC \leqslant d(B, S')=BC', from BB we can continue to CC. There we will replenish the gasoline spent on the path BCBC, and d(C,S)=CA<d(B,S)d(C, S')=CA'<d(B, S'), so we can still reach SS', namely the station AA'. Further one can go to BB', and from there (as before) to CC'. We obtain the route ABCABCABC A'B'C'.

It remains to construct a counterexample for n4n \geqslant 4. We shall assume that the half-circumference of the planet equals 11. Let us arrange the stations A2,A3,,AnA_2, A_3, \ldots, A_n along a great circle so that A2A3=A3A4==An1An=d<1n1A_2A_3=A_3A_4=\cdots=A_{n-1}A_n=d<\frac{1}{n-1}, and the station A1A_1 so that A1A3=dA_1A_3=d and A1A2=A1A4A_1A_2=A_1A_4. Again denote S={A1,,An}S=\{A_1, \ldots, A_n\} and S={A1,,An}S'=\{A_1', \ldots, A_n'\}. Let us supply the stations A1,A1,,An1,An1A_1, A_1', \ldots, A_{n-1}, A_{n-1}' with enough gasoline to cover a distance of dd, and the stations AnA_n and AnA_n' with gasoline to cover a distance of 1(n1)d1-(n-1)d. From every station one can reach the diametrically opposite one: indeed, for 2in2 \leqslant i \leqslant n the route AiAi+1AnA2A3AiA_iA_{i+1}\ldots A_nA_2'A_3'\ldots A_i' is possible, and the route A1A3A4AnA2A3A1A_1A_3A_4\ldots A_nA_2'A_3'A_1' is also possible. On the other hand, at each of the stations A1,,An1A_1, \ldots, A_{n-1} there is only just enough gasoline to reach the nearest station, and at AnA_n and AnA_n' just enough to cross over into the other set. Therefore, in order to visit all stations, at least one of the sets, say SS, would have to be visited entirely without using the fuel at AnA_n, but for that a path longer than (n1)d(n-1)d would need to be traveled, while there is gasoline only for a path of length (n1)d(n-1)d.

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 translated into English from sr; metadata (topic, difficulty) added by this project.