Track / Stage 5 / 334 of 400 #934 of 2000

Problem 934

AIME late

Combinatorics Difficulty 5.8 Prove it

5.48 Suppose in a certain galaxy there are an odd number of planets, and each planet has an astronomer observing the nearest planet, with the distances between planets all being unequal. Prove that there is one planet that is not observed.

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

[Proof] Let the number of planets be $n$ , and let planets $A$ and $B$ be the closest pair among all planet pairs, so the astronomers on these two planets are observing each other.

Consider the remaining $n-2$ planets and their astronomers. If one of these astronomers is observing either $A$ or $B$ , then it is clear that there must be one planet that is not being observed. If no one is observing $A$ or $B$ , then we can use the same method to select another two planets from the $n-2$ planets, such that the astronomers on these two planets are observing each other. And so on. Since $n$ is odd, there must be one planet that is not being observed.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.