combinatoricspigeonhole-principle
The question I am looking at:
Prove that given 5 points inside a square of side length 2, it is always possible to find two of them whose distance apart is at most $\sqrt2$.
This looks to me like I should try to apply the Pigeonhole Principle, though I can't see a way to do it. If anyone can send me in the right direction?…
Putting $10$ points in a square of size $1$ such that the minimal distance $d_{\text{min}}$ between two points is maximized, is exactly the same as finding an arrangement of $10$ non-overlapping disks of radius $r=d_{\text{min}}/2$ with center in the unit square with the maximum radius possible (look at the second picture below). Note that these disks are getting out of the unit square but form the most dense packing of $10$ spheres of the square of size $1+2r$. So the problem is equivalent to the disk packing in a square. According to wikipedia (or directly the exhaustive main reference of the wikipedia article), the best known packing of $10$ spheres in a square gives us a minimal distance $$d_{\text{min}}= 0,421...$$ This is significantly better then the original bound $\sqrt{2}/3=0.47...$ found by the grid and pigeon hole principle.
Before finding the Wikipedia article I played with geogebra and the best packing I found is the one below, one can compute the radius and find $d_{\text{min}}=(\sqrt{2 \left(1+2 \sqrt{2}\right)}-2)/(2 \left(2 \sqrt{2}-1\right))=0.419...$ which is not as good as the one mentioned aboved (you want to maximize $d_{\text{min}}$).
This seems sufficient, but you can add something like this:
The distance between two points in an equilateral triangle with side length $1$ is at most $1$ because this triangle lies in a circle of radius $1/2$.
Best Answer
Credit to @Gerry_Myerson for inspiration.
We have a 2x2 square. We want to split this into 4 1x1 squares, simply by joining the centres of opposite sides. This creates a small grid.
Now imagine we want to insert our 5 points into these 4 1x1 squares. Here we apply the pigeonhole principle. Since we have more points than squares to place them, we know that some square must end up containing at least 2 points.
So now we know that given any 5 points inside a square of side length 2, we can find two of them that lie in some square of side length 1. What is the maximum distance apart that these can be? It's obvious (and prove-able, though I won't do it here) that the two points are maximum distance apart when they lie on opposite corners. By simple Pythagoras', we know that the length of the diagonal of a square of side length 1 is $\sqrt2$, so we have the required result.