Proving "At Least One Planet Unobserved in Planetary System

[Doom of Doom]

"On each planet in a planetary system of an odd number of planets, there is an astronomer observing the nearest planet. Assume the distances between each pair of planets are all different. Prove that there is at least one planet that is not being observed by any astronomer."


This seems like it should be really easy, but I'm just not quite sure how to do it.
I think it has something to do with the well-ordering principle.

Anyway, in a system of n planets, there will be a total of n(n-1)/2 pairs of planets, and all of the distances between each of the pairs will be different.

Where do I go from here?

 

[Dick]

Start with the case of three planets. Then do five. Once you've got that, the general case should be easy.

 

[Doom of Doom]

Ok, so I did do the first few cases. I just can't figure out a good way to generalize it.

So, say you have n planets, and we denote the distance between planets i and j by i,j.
Then assume that planets 1 and 2 are the closest pair. So, 1,2 is the smallest over all i,j's. We can then think of planets 1 and 2 as the same planet, that is planet (1,2). Then the distance from the ith planet to planet (1,2) will be i,(1,2) = min(i,1, i,2).

We can then do this minimalizing process again, to reduce us down to the n-2 case.

Thus, it can be proved by induction.

Is this a good outline for a proof?

 

[Dick]

That's basically the idea. Except there is a difference between the pair 1,2 and a planet. A planet observes somebody else. The pair doesn't. So you can't strictly reduce it from n to n-1, unless you allow for nonobserving planets. Is the statement still true if you allow for them?

 

[Dick]

You know, the more I think about this, the more awkward it becomes to write down. It is starting to sound more and more like an ordering argument.

 

[D H]

Ok, so I did do the first few cases. I just can't figure out a good way to generalize it.

The conjecture is obvious for the case N=1. If you don't like that case, start with N=3. There are three pairings for N=3 and thus three interplanetary distances. Since the interplanetary distances are unique (given condition), one of these distances is shorter than other of the either of the others (well-ordering principle). These two planets must observe one another. Nobody is left to observe the more remote planet.

Now assume the conjecture is true for some odd number N. What about N+2? Use the same argument as for N=3. One of the interplanetary distances is shorter than any of the others. These two planets must observe one another, which means the other N planets must mutually observe all of those other N planets. They can't do this by assumption that the conjecture is true for N. Since the conjecture is true for N=1 (or N=3, take your pick), the conjecture is true for all positive odd N by induction.

 

[HallsofIvy]

If there is no planet not being observed, then there must be not be any planet being observed by more than one planet. Now a crucial point is that, since distance is symmetric, the two planets closest together must be observing each other. Since they are both observed, we can drop them from consideration, giving the same problem for n-2 planets. But the same thing is true for these n -2 planets so we can do it again. Eventually, we get to a single planet which is not being observed- and in fact, not observing any one! Our assumption that there was no planet being observed by more than one other planet cannot be true so there must be a planet not being observed.

 

[Dick]

Try thinking of it this way. Suppose everybody is observed. As you've pointed out, the closest pair observe each other. Now consider the remaining n-2 objects. There are two possibilities. i) Someone in the n-2 group observes the pair. But now you've got only n-3 observers for n-2 objects (since someone is busy watching the pair), so someone in the n-2 group must be unobserved. ii) No one in the n-2 group is watching the pair. In this case you can go ahead with the induction.

 

[HallsofIvy]

Dick, I think we are walking in each others shoes!

 

[e(ho0n3]

This is a nice problem involving both proof by induction and contradiction. Doom of Doom: where did you get this problem from?

 

[Doom of Doom]

Ah! Thank you so much! I see it now.

My professor put this as one of the review problems for my Introduction to Abstract Mathematics exam. I'm kinda worried about how hard the exam might be, if this was on the review!

 

[D H]

The proofs so far have used the well-ordering principle, which is equivalent to the axiom of choice. A proof without reverting to the axiom of choice is possible.

A preliminary observation: The system in question must comprise at least two planets, as there are no astronomers in a system with zero planets and no planets to observe in a system with only one planet. Since the number of planets is odd, the system must comprise at least three planets.

Consider the problem from the perspective of graph theory. Construct a digraph with each node representing a planet and each directed edge representing the planet observed by an astronomer on some planet. Since astronomers observe some planet other than their own, the resulting graph is simple. Since each planet has one astronomer, the number of outgoing edges is equal to the number of planets. To be fully observed, each planet must have at least one incoming edge. This condition can only be satisfied if the graph is 2-regular (every node has one incoming and one outgoing edge). A 2-regular graph comprises a set of disjoint cycle graphs. Since all planets are connected to at least one other planet, the disjoint cycle graphs that represent a full-observed system must contain at least two nodes.

A cycle graph with two nodes can obey the constraint that astronomers observe the closest planet. Since distance is symmetric and "less than" is transitive, a cycle graph with more than two nodes breaks the constraint that astronomers observe the closest planet if the distances between planets are unique. As noted above, all systems in which all planets are observed are 2-regular graphs with at least two nodes in each of the component cycle graphs. If N, the number of nodes (planets), is an odd number greater than two, at least one of these component cycle graphs must contain an odd number of nodes n such that n>=3. Since any cycle graph with more than two nodes violates the constraint that all astronomers observe the closest planet, a system with an odd number of planets cannot be fully observed with this constraint in place.

 

[Dick]

Hi, DH. That's fine. But you don't really need the axiom of choice when you are dealing with finite sets, do you?

 

[D H]

You invoked the axiom of choice in saying "the closest pair observe each other". Saying that requires the well-ordering principle, and the well-ordering principle is equivalent to the axiom of choice.

 

[Dick]

I'm just asking for fun, but why do I need a 'well ordering principle'? First I pick the smallest member of a finite set which I already know is well ordered, then I pick the second smallest. Again, I thought axiom of choice issues were concerned only with infinite sets.

 

[D H]

I'm just asking for fun, but why do I need a 'well ordering principle'? First I pick the smallest member of a finite set which I already know is well ordered, then I pick the second smallest. Again, I thought axiom of choice issues were concerned only with infinite sets.

How do you know the set is already well-ordered? Without proving that the set is well-ordered you are implicitly invoking Zorn's lemma or the well-ordering principle, both of which are equivalent to the axiom of choice. The axiom of choice implicitly rears its head in a number of unexpected places. I suspect it may even be rearing its ugly head in my graph theoretic proof as my proof implicitly uses the law of the excluded middle.

 

[Dick]

How do you know the set is already well-ordered? Without proving that the set is well-ordered you are implicitly invoking Zorn's lemma or the well-ordering principle, both of which are equivalent to the axiom of choice. The axiom of choice implicitly rears its head in a number of unexpected places. I suspect it may even be rearing its ugly head in my graph theoretic proof as my proof implicitly uses the law of the excluded middle.

The set of distances is a finite subset of the reals. It gets it's ordering from the reals which I seem to remember are well ordered. You're proof ought to be safe as well, just because it's about finite graphs. It has to be. The conclusion isn't true if you have an infinite number of planets.