0
$\begingroup$

how would I prove this exercise: If we had five points in a square with sides of length one. How can we use the Pigeonhole Principle to prove that there are two of these points having distance at most 1/$\sqrt {2}$

$\endgroup$
  • 1
    $\begingroup$ Five is a suspicious number. Put four of the points in the corners of the square (furthest apart, in some pigeon holes). The furthest an extra point can be from all of the previous four is in the center. Is that the correct distance? $\endgroup$ – bimmo Sep 30 '14 at 9:27
1
$\begingroup$

Divide the square into quarters. Let 4 points be at the corners of the original larger square. Now, clearly the maximum distance is the line from a corner of the larger square to its centre. This distance is $\frac{1}{\sqrt2}$ units. Therefore, there are at least 2 points with distance $d$, such that

$0<d\leq\frac{1}{\sqrt2} \square$

$\endgroup$
1
$\begingroup$

Other posters assume (without proof) that a maximal configuration will have four of the points at the corners of the square. But this is not necessary.

Divide the square into four smaller squares in the obvious way. Then, by the pigeonhole principle, there must be a square that contains at least two of the five points. The diagonal of each smaller square is $\dfrac{1}{\sqrt 2}$, so the distance between these two points is at most $\dfrac{1}{\sqrt 2}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.