# proving using pigeon hole principle

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}$

• 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? – bimmo Sep 30 '14 at 9:27

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$
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}$.