Maximum number of ufo that can visit any planet

84 Views Asked by At

Consider an infinite alien 2d world consisting of infinite planet, so that distance between any two planets is not same. Now at some point of time, a ufo leaves each planet and goes to planet nearest to it. Only one ufo leaves each planet. Find the maximum number of ufo that can land on any planet.

For this question, I found the critical condition of a hexagon inscribed inside a circle with centre as planet P. Now, in this case all distances are equal. So by intuition, it appears that maximum no of ufo that can land on P should be 5 planets $p_i$, each lying so as to satisfy constraints.

Is my reasoning correct?

1

There are 1 best solutions below

2
On

Your intuition seems correct, but as it is written your argument is far from rigorous. Let me get you started on a (thoroughly) rigorous argument:

Consider a configuration of planets where the maximum number of UFO's on one planet is achieved. Let $M$ be a planet with the maximum number of UFO's. Let $P_1$ be the nearest planet from which a UFO came to $M$ (clearly the maximum is at least $1$). Then all other planets from which the UFO's on $M$ came are closer to $M$ than to $P_1$, but farther from $M$ than $P_1$. That is, they are outside the blue region in the image below:

enter image description here

Now let $P_2$ be a second planet from which a UFO came to $M$. Then the angle $\angle P_1MP_2$ is greater than...