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.
Briefly, consider small numbers of planets, whether even or odd.
If there is only 1 planet, no one is observing it, the proposition is True.
If there are 2 planets, each is the other's closest and each is being observed (for one case of an even number of planets, the proposition fails).
If there are 3 planets, wlog, let A be at the origin, and B is at (1,0,0) and moreover let B be A's closest. A is observing B. C is anywhere on the sphere centered at the origin and with radius r such that r (wlog) is greater than 1 (except not on the plane that is the perpendicular bisector of AB). If distance BC < 1, then no one is observing A. But if distance BC > 1, then no one is observing C. BC is not = 1 according to the statement of the problem. Thus for 3 planets, the proposition still holds.
Now use 3 planets as the base case for a proof by induction.
Assume that for some odd number of planets "M", the proposition is True: one planet, "X" is not being observed. ('M' because if there are astronomers on them, they are probably M-Class planets).
Add 2 planets.
If the 2 planets are 'very close together' they watch each other and the rest are unchanged. Still True.
This is as far as I got with induction.
Part 2: Somewhat hand-waving argument. If every planet has a virtual directional string connecting it to its closest neighbor, it is observing the planet the string is pointing to. I think the only topological configurations you can have are: 2-planet loops and multiple planet strings of 3 or more. I think if you add a planet close enough to a 2 planet loop, it will just break that loop and form a 3 planet chain. Every chain has a head and a tail, with no planet observing the head planet. The only way to have no unobserved planet is for all planets to be part of a 2 planet loop, ie an even number of planets. But this is a not rigorous proof yet.
Edited on May 1, 2023, 11:50 pm
Posted by Larry
on 2023-05-01 23:42:39