Serbian Mathematical Olympiad

Solution:

The answer is $n \leqslant 3$.
The station diametrically opposite to station $X$ will be denoted by $X'$.

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

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

(1) Suppose that from station $A$ via the path $AB$ one cannot reach the set $S'$. One also cannot reach $S'$ via $AC$ - otherwise it would also be possible via $ABC$, since $BC \leqslant AC$, and at $B$ there is enough gasoline to make up for the consumption on the path $AB$. Hence, starting from station $A$, one can reach $S'$ only directly. The nearest point of the set $S'$ is $C'$, so the entire route $CBA C'B'A'$ is possible. The case when from $A'$ via the path $A'B'$ one cannot reach $S$ is analogous.

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

It remains to construct a counterexample for $n \geqslant 4$. We shall assume that the half-circumference of the planet equals $1$. Let us arrange the stations $A_2, A_3, \ldots, A_n$ along a great circle so that $A_2A_3=A_3A_4=\cdots=A_{n-1}A_n=d<\frac{1}{n-1}$, and the station $A_1$ so that $A_1A_3=d$ and $A_1A_2=A_1A_4$. Again denote $S=\{A_1, \ldots, A_n\}$ and $S'=\{A_1', \ldots, A_n'\}$. Let us supply the stations $A_1, A_1', \ldots, A_{n-1}, A_{n-1}'$ with enough gasoline to cover a distance of $d$, and the stations $A_n$ and $A_n'$ with gasoline to cover a distance of $1-(n-1)d$. From every station one can reach the diametrically opposite one: indeed, for $2 \leqslant i \leqslant n$ the route $A_iA_{i+1}\ldots A_nA_2'A_3'\ldots A_i'$ is possible, and the route $A_1A_3A_4\ldots A_nA_2'A_3'A_1'$ is also possible. On the other hand, at each of the stations $A_1, \ldots, A_{n-1}$ there is only just enough gasoline to reach the nearest station, and at $A_n$ and $A_n'$ just enough to cross over into the other set. Therefore, in order to visit all stations, at least one of the sets, say $S$, would have to be visited entirely without using the fuel at $A_n$, but for that a path longer than $(n-1)d$ would need to be traveled, while there is gasoline only for a path of length $(n-1)d$.