On a spherically shaped planet there are 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 such that, for any arrangement of 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 .
The station diametrically opposite to station will be denoted by .
For the claim is trivial. Let and let be the smallest among all distances between two stations. From station one can reach , say via the path (the case of the path is similar), but at there is enough gasoline to drive to the station nearest to it, which is , so the route is possible.
Let us prove the claim for and six stations . Let be the smallest among the distances between two stations, and let be the station nearest to . Denote and . Starting from any station of one set, one can reach the other set.
(1) Suppose that from station via the path one cannot reach the set . One also cannot reach via - otherwise it would also be possible via , since , and at there is enough gasoline to make up for the consumption on the path . Hence, starting from station , one can reach only directly. The nearest point of the set is , so the entire route is possible. The case when from via the path one cannot reach is analogous.
(2) If case (1) does not hold, let us start from straight to . Since the set is within reach, and , from we can continue to . There we will replenish the gasoline spent on the path , and , so we can still reach , namely the station . Further one can go to , and from there (as before) to . We obtain the route .
It remains to construct a counterexample for . We shall assume that the half-circumference of the planet equals . Let us arrange the stations along a great circle so that , and the station so that and . Again denote and . Let us supply the stations with enough gasoline to cover a distance of , and the stations and with gasoline to cover a distance of . From every station one can reach the diametrically opposite one: indeed, for the route is possible, and the route is also possible. On the other hand, at each of the stations there is only just enough gasoline to reach the nearest station, and at and just enough to cross over into the other set. Therefore, in order to visit all stations, at least one of the sets, say , would have to be visited entirely without using the fuel at , but for that a path longer than would need to be traveled, while there is gasoline only for a path of length .