A puzzle by V. Dubrovsky, from Quantum, January-February 1992:
In a certain planetary system, no two planets are separated by the same distance. On each planet sits an astronomer who observes the planet closest to hers.
Prove that if the total number of planets is odd, there must be a planet that no one is observing.
We make a list of all the planets a,b,c,... and their distances A,B,C,... in rows in this order as follows.
1. Planet a, closest neighbour, planet b, distance A. We call this planet the 'Prime' for the entry.
2. Next closest neighbour of a is c, distance B. (B>A)
3. Next closest neighbour of b is d, Distance C. (C<B)
This arrangement must always be possible, since all the distances are different. It must also be unique for any Prime.
Since all the distances are different, there must be a pair (the closest pair of all) that observe each other. And indeed that will be true whenever the distance in row 1 is less that the distances in rows 2 and 3. We can eliminate all such pairs and their corresponding planets, since they can't be observing anything else but each other.
If all the planets are now eliminated, then we are done - but in that case the number of planets must be even.
Let j be a Prime not eliminated by pairing, in the sequence i,j,k,l. j looks at k but k does not look at j because l is closer to k. Otherwise j and k would be a pair. So l is closer to k than j. And by parity of reasoning, i must be further from j than k. Planet i must also be a planet not eliminated by pairing, because otherwise j would have no observer. The same must be true of all such entries.
We can now return to the list and find the Prime for which distance B is the largest. The Prime cannot be observed by the planet at distance B, because by definition some other planet must be closer to that planet. Therefore the Prime is unobserved.
So we have the rather cool result that if the planets are not in pairs, then at least one of them is always unobserved, irrespective of the parity of the number of planets.
Edited on May 3, 2023, 11:40 pm
Posted by broll
on 2023-05-02 11:36:51