My instructor asked us to:
Show that for any set of 10 points choosen within a square of side length 3 units, there exists 2 points whose distance is at most $\sqrt{2}$ units.
He solved it using Pigeon Hole Principle.
But I am going by a different route.
What I understand from the question is that for any distribution of points, for the closest pair of points there is an upper limit for the possible distance between them. They can't be farther than that upper limit.
So I start putting the points one by one by making sure that I am putting them at the maximum distance possible from the closest point. Taking the square as $ABCD$:
- First 2 points are on $A$ and $C$
- third and fourth points on $B$ and $D$
- fifth at the center
- points sixth to ninth on the midpoints of the sides of the square.
My distribution for the first 9 points is having the most distances between any 2 points. Now for the tenth point, maximum distance is possible when we put it halfway between the central point and one of the corner points. The distance is this case comes out to be $\frac{3}{4}\sqrt{2}$ which is smaller than $\sqrt{2}$.
What I am trying to establish with my solution is that there is a more stricter limit to the distance we are trying to find in the original question.
Greed is not always the best strategy. The below pattern has $\frac 54$ as minimal distance.