Maths Olympiad Prep

Library / /359 of 520

Combinatorics Difficulty 5.8 AIME, harder Find the answer

5. On the surface of a spherical planet, there are 2n2 n gas stations, whose positions are symmetric about the center of the sphere (i.e., for each gas station, there is a corresponding gas station at its symmetric point about the center). Each gas station stores a certain amount of fuel, and the fuel is non-renewable. It is known that a car with an initially empty (and infinitely large) fuel tank can start from any gas station, choose an appropriate route, refuel at the gas stations along the way, and reach the gas station symmetric to the starting point. Here, it is assumed that the car consumes a constant amount of fuel per unit length traveled.

Under the above conditions, find the value of nn such that the car can definitely traverse all the gas stations on the planet in some way (the starting and ending points are not restricted).

A number or a short expression. Spacing and $ signs are ignored.

Solution

5. n=1,2,3n=1,2,3.

Let XX^{\prime} denote the gas station symmetric to XX with respect to the center of the sphere.
When n=1n=1, the conclusion is obviously true.
For n=2n=2, let AB=ABA B=A^{\prime} B^{\prime} be the minimum spherical distance between two gas stations.

By the given condition, a car starting from AA can reach AA^{\prime}. Assume this path is ABAA \rightarrow B^{\prime} \rightarrow A^{\prime} (the path ABAA \rightarrow B \rightarrow A^{\prime} is similar). The fuel at BB is sufficient for the car to travel to the nearest gas station AA, thus, BABAB \rightarrow A \rightarrow B^{\prime} \rightarrow A^{\prime} is a feasible path.

For n=3n=3, let the six gas stations be A,A,B,B,C,CA, A^{\prime}, B, B^{\prime}, C, C^{\prime}. As shown in Figure 3, let AB=ABA B=A^{\prime} B^{\prime} be the minimum spherical distance between two gas stations, and assume BB is the nearest gas station to CC. Divide all gas stations into two groups:
S={A,B,C},S={A,B,C}, S=\{A, B, C\}, S^{\prime}=\left\{A^{\prime}, B^{\prime}, C^{\prime}\right\},

A car starting from any gas station can reach the other group.
(1) If a car starting from AA cannot reach SS^{\prime} via the path ABA \rightarrow B, then it also cannot reach SS^{\prime} via the path ACA \rightarrow C, otherwise, the path ABCSA \rightarrow B \rightarrow C \rightarrow S^{\prime} would be feasible (since the fuel at BB is not less than the consumption of the path ABA \rightarrow B, and BCACB C \leqslant A C). Therefore, a car starting from AA can only directly reach SS^{\prime}. The nearest gas station in SS^{\prime} to AA is CC^{\prime}, thus, the path CBACBAC \rightarrow B \rightarrow A \rightarrow C^{\prime} \rightarrow B^{\prime} \rightarrow A^{\prime} is feasible.

Similarly, if a car starting from AA^{\prime} cannot reach SS via the path ABA^{\prime} \rightarrow B^{\prime}, then the path CBACBAC^{\prime} \rightarrow B^{\prime} \rightarrow A^{\prime} \rightarrow C \rightarrow B \rightarrow A is feasible.
(2) If the assumption in (1) does not hold, then the car can first travel directly from AA to BB. Since SS^{\prime} is still reachable, and BCBC=d(B,S)B C \leqslant B C^{\prime}=d\left(B, S^{\prime}\right), the car can continue from BB to CC.
The fuel at CC is not less than the consumption of the path BCB \rightarrow C, and
d(C,S)=CABC=d(B,S), d\left(C, S^{\prime}\right)=C A^{\prime} \leqslant B C^{\prime}=d\left(B, S^{\prime}\right),

Thus, after reaching CC, SS^{\prime} is still reachable, and the nearest gas station in SS^{\prime} to CC is AA^{\prime}.

Therefore, the path ABCABCA \rightarrow B \rightarrow C \rightarrow A^{\prime} \rightarrow B^{\prime} \rightarrow C^{\prime} is feasible.
The above proves that n=1,2,3n=1,2,3 all satisfy the requirements.
Next, construct a counterexample for n4n \geqslant 4.
As shown in Figure 4, assume the half-circumference of a great circle on the planet is 1.

Place the gas stations A2,A3,,AnA_{2}, A_{3}, \cdots, A_{n} on a great circle, and satisfy
A2A3=A3A4==An1An=d<1n1, A_{2} A_{3}=A_{3} A_{4}=\cdots=A_{n-1} A_{n}=d<\frac{1}{n-1},

and arrange the position of gas station A1A_{1} such that
A1A3=d, and A1A2=A1A4 A_{1} A_{3}=d \text {, and } A_{1} A_{2}=A_{1} A_{4} \text {. }

Assume the gas stations A1,A1,,An1,An1A_{1}, A_{1}^{\prime}, \cdots, A_{n-1}, A_{n-1}^{\prime} each store the fuel required to travel a distance dd, and AnAnA_{n} 、 A_{n}^{\prime} each store the fuel required to travel a distance 1(n2)d1-(n-2) d. Then a car starting from any gas station can reach the symmetric gas station. The corresponding feasible paths are
A1A3A4AnA2A3A1 and AiAi+1AnA2A3Ai, \begin{array}{ll} & A_{1} \rightarrow A_{3} \rightarrow A_{4} \rightarrow \cdots \rightarrow A_{n} \rightarrow A_{2}^{\prime} \rightarrow A_{3}^{\prime} \rightarrow A_{1}^{\prime} \\ \text { and } & A_{i} \rightarrow A_{i+1} \rightarrow \cdots \rightarrow A_{n} \rightarrow A_{2}^{\prime} \rightarrow A_{3}^{\prime} \rightarrow \cdots \rightarrow A_{i}^{\prime}, \end{array}

where 2in2 \leqslant i \leqslant n.
However, let
S={A1,A2,,An},S={A1,A2,,An}, S=\left\{A_{1}, A_{2}, \cdots, A_{n}\right\}, S^{\prime}=\left\{A_{1}^{\prime}, A_{2}^{\prime}, \cdots, A_{n}^{\prime}\right\},
then the fuel at each of A1,A2,,An1A_{1}, A_{2}, \cdots, A_{n-1} is only sufficient for the car to travel to the nearest gas station, and the fuel at AnAnA_{n} 、 A_{n}^{\prime} is only sufficient for the car to travel to the other group (AnA_{n} to A2A_{2}^{\prime}, AnA_{n}^{\prime} to A2A_{2}). Therefore, to visit all gas stations, a car starting from SS can only visit all gas stations in SS without using the fuel at AnA_{n}, which is impossible.
A car starting from SS^{\prime} is similar.
This provides a counterexample for n4n \geqslant 4.
In summary, the values of nn that satisfy the requirements are only 1,2,31, 2, 3.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.