Circles covering squares and points
The following question appeared in an issue of π in the Sky:
Show that given any 201 points inside a 10-by-10 square, there is a unit circle containing at least 3 of those points.
It is natural to ask, for what other number of points n does the above hold? And what is the smallest such n?
One way to bound n geometrically follows from noticing the obvious fact that
given k circles covering a square and m points inside that square with any individual circle containing at most two of them, then it must be the case that m ≤ 2k.
which is just a restatement of the fact that
So it is sufficient to produce a covering of the square by 100 unit circles to prove the original statement, i.e. when n = 201.
Two-hundred and one turns out to be a very generous bound, though. It’s quite easy to construct a covering of 60 (maybe 61?) circles, by an arrangement similar to the one below:
Tiling this arrangement of unit circles allows you cover a 10-by-10 square with 60 of them
This allows us to reduce the number of points from 201 in the original puzzle to only 2*60 + 1 = 121.
How much further can we reduce this number by this method? Worded slightly differently, what is the smallest number of unit circles that can cover a 10-by-10 square? This turns out to be a difficult problem, and Erich’s Packing Center has the answer for the opposite question (that is, “what is the largest s-by-s square that n unit circles can cover?”) for small values of n, with s reaching values of only about half of in what we’re interested.
Using Wolfram Alpha, we can plot these values and observe that s appears to increase approximately linearly with n, and perform a linear fit. Solving the resulting equation for s = 10, we might expect that a covering of a 10-by-10 square is possible using only 27 unit circles, which if true would bring the bound proved above down from 121 to only 55.
Finding such coverings allows us to prove that the original statement holds for (say) all n ≥ 121, but would finding the optimal covering give us the smallest n for which it holds? That doesn’t seem obvious, as this method essentially gives us a fixed set of circles we are allowed to use, independent of the points in the square, while the original statement allows for the circle to be a function of the points. So can we prove anything directly from the statement itself?
Again, it doesn’t seem obvious how, but what we can do easily is prove that the original statement fails for n ≤ 49. Simply consider a square lattice of points separated horizontally and vertically by a distance of 
, so that each point is separated diagonally by at least a distance of 2. If we take ε to be small enough, say ε = 0.1, we can fit a grid of 7*7 = 49 points inside a 10-by-10 square, and it’s easy to convince yourself that no unit circle can cover three of the points in the lattice.
Spacing each point apart horizontally and vertically by √2+ε units ensures that no unit circle will cover three points
So we have an interesting situation: we can prove that the statement fails for all n ≤ C by constructing sets of points, and prove that the statement holds for all n ≥ C by constructing sets of circles, but neither method easily provides an exact answer.
Can we do better?