Proving "At Least One Planet Unobserved in Planetary System

In summary: I guess that's the word I was looking for.In summary, the problem states that on each planet in a planetary system of an odd number of planets, there is an astronomer observing the nearest planet. The goal is to prove that there is at least one planet that is not being observed by any astronomer. Through using various techniques such as proof by induction, contradiction, and graph theory, it can be shown that the statement is true for all odd numbers of planets. This can be done without relying on the axiom of choice, making for a stronger and more elegant proof.
  • #1
Doom of Doom
86
0
"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?
 
Physics news on Phys.org
  • #2
Start with the case of three planets. Then do five. Once you've got that, the general case should be easy.
 
  • #3
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?
 
  • #4
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?
 
  • #5
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.
 
  • #6
Doom of Doom said:
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.
 
  • #7
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.
 
  • #8
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.
 
  • #9
Dick, I think we are walking in each others shoes!
 
  • #10
This is a nice problem involving both proof by induction and contradiction. Doom of Doom: where did you get this problem from?
 
  • #11
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!
 
  • #12
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.
 
  • #13
Hi, DH. That's fine. But you don't really need the axiom of choice when you are dealing with finite sets, do you?
 
  • #14
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.
 
  • #15
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.
 
  • #16
Dick said:
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.
 
  • #17
D H said:
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.
 

1. How do scientists prove the existence of an unobserved planet in a planetary system?

Scientists use a variety of methods to prove the existence of an unobserved planet in a planetary system. This can include studying the gravitational effects of the planet on other objects in the system, analyzing data from telescopes and satellites, and using mathematical models to predict the presence of the planet based on observations.

2. What evidence is used to support the existence of an unobserved planet?

The most common evidence used to support the existence of an unobserved planet is gravitational perturbations. This is when the gravitational pull of the planet causes changes in the orbits of other objects in the system. Other evidence can include the presence of dust and debris in the system, as well as patterns in the movement of objects that can be explained by the presence of an unseen planet.

3. Can scientists be certain that there is an unobserved planet in a planetary system?

While scientists can use strong evidence to support the existence of an unobserved planet, they cannot be 100% certain without direct observation. However, the use of multiple methods and careful analysis can greatly increase the confidence in the existence of an unobserved planet.

4. How do scientists determine the size and characteristics of an unobserved planet?

Scientists can use data from various sources, such as telescopes and satellites, to estimate the size, mass, and other characteristics of an unobserved planet. This can also be done through mathematical models and simulations. The more data that is collected and analyzed, the more accurate the estimates can become.

5. What implications does the discovery of an unobserved planet have on our understanding of the universe?

The discovery of an unobserved planet can have significant implications on our understanding of the universe. It can provide valuable insights into the formation and evolution of planetary systems, as well as the potential for habitable worlds outside of our own. It can also expand our understanding of the diversity of planets and their potential for supporting life.

Similar threads

  • Astronomy and Astrophysics
Replies
3
Views
1K
Replies
12
Views
2K
  • Beyond the Standard Models
Replies
5
Views
2K
Replies
16
Views
2K
Replies
2
Views
1K
  • Sci-Fi Writing and World Building
Replies
21
Views
981
  • Calculus and Beyond Homework Help
Replies
1
Views
493
  • Special and General Relativity
2
Replies
58
Views
3K
Replies
17
Views
2K
Back
Top