In the planetary system of the star Zoolander there are $2015$ planets. On each planet an astronomer lives who observes the closest planet into his telescope (the distances between planets are all different). Prove that there is a planet who is observed by nobody.
Problem
Source:
Tags: combinatorics
OGT2020
13.11.2021 00:43
We know that each astronomer must be looking at an adjacent planet.
Pigeonhole
principle here.
physicskiddo
13.11.2021 00:44
What happens if an astronomer is equidistant from two planets? I would assume he would observe neither, as they are both the 'closest'?
OGT2020
13.11.2021 02:07
I think we should assume all distances are different.
If all planets are observed, every planet must be looked at by only one person, since there are an equal number of planets and astronomers. If we can prove that at least one planet is observed by more than one person, then we can conclude one planet is not observed due to the Pigeonhole Principle.
greenturtle3141
13.11.2021 02:54
Assume otherwise, so every planet is watched by someone. Enumerate the planets as $1,2,\cdots,2015$ and let $f(n)$ be the planet that is watched by the observer on planet $n$.
What kind of function is $f$?
Consider cycles, and beware the number $2$.
OGT2020
16.11.2021 00:12
greenturtle3141 wrote:
Assume otherwise, so every planet is watched by someone. Enumerate the planets as $1,2,\cdots,2015$ and let $f(n)$ be the planet that is watched by the observer on planet $n$.
What kind of function is $f$?
It's a bijection. That really makes me want to use Pigeonhole. greenturtle3141 wrote:
Consider cycles, and beware the number $2$.
We cannot have a cycle greater than 2, since that would require an astronomer looking at a non-adjacent planet, which is impossible. However, we cannot only have cycles of length 2, since we have an odd number of planets/astronomers, and since we cannot have cycles other than length 2 (length 1 requires someone observing themself, dumb and impossible), we have a contradiction.
I think I'm done, but I need to formalize it now.
greenturtle3141
16.11.2021 01:32
Yes, that is essentially the correct idea.
OGT2020
16.11.2021 19:57
Assume that each planet is observed, for a proof by contradiction. If we then take each astronomer and assign them a planet, we have a bijection. Inside this bijections, there must be cycles - but these cycles must be of length 2, as no one can observe themself and and cycle larger than length 3 means someone has to observe a non-adjacent planet, which is impossible. However, since there are an odd number of planets, we cannot have cycles of length 2 only. Therefore, we have a contradiction, and not every planet can be observed by an astronomer.
Also, I just finished the AMC 12, and I did pretty bad. Next time, baby.
greenturtle3141
16.11.2021 22:41
OGT2020 wrote: but these cycles must be of length 2, as no one can observe themself and and cycle larger than length 3 means someone has to observe a non-adjacent planet, which is impossible. You should recognize that this is the key point in the argument. Justify this in particular!
mathboy100
17.11.2021 02:25
parmenides51 wrote: In the planetary system of the star Zoolander there are $2015$ planets. On each planet an astronomer lives who observes the closest planet into his telescope (the distances between planets are all different). Prove that there is a planet who is observed by nobody.
First, note that if one planet is being watched twice, then another is being watched zero times. Assume that the problem statement is false, that every planet is being watched by someone.
Take the two closest planets, and remove them from the set of planets. Note that this can be done, because both planets are watching each other, but no other planet is.
Continue doing this until there is one planet left. This planet is watching nobody.
However, the planet that this particular planet was watching before the removal must have been watched twice in the original configuration. Thus, we have a contradiction.
Alternatively, no planet would've been watching the last planet. This is also a contradiction.
pog
17.11.2021 03:22
greenturtle3141 wrote: Hypatia1728 wrote: lol, it's ez Extremely rude and unnecessary. Think about what you say next time. i don't see how it's extremely rude
Hypatia1728
18.11.2021 02:47
^^yeah...? If you've noticed, that's not the only thing I've written, by the way. And a question that's basically identical to an AoPs question would be easier. (It actually doesn't make sense to post an identical question honestly)
Hypatia1728
18.11.2021 03:12
Also, @all you didn't really need to go into anything complex like functions or cycles for this problem. I can tell you a much simpler strategy (the AoPs one tbh) if anyone wants to know.
Hypatia1728
18.11.2021 12:46
There's nothing to be offended about the fact that someone else can find a problem easy which you find tough. There are a lot of people who find the same questions very trivial which I may find very tough, but if one starts getting angry about that, you'll never get anywhere. We all have different exposure and different skill levels, and there will always be people finding different things difficult or easy. That doesn't mean anyone's insulting you with their opinion.