Problem:
A square grid on the Euclidean plane consists of all points , where and are integers. Is it possible to cover all grid points by an infinite family of discs with nonoverlapping interiors if each disc in the family has radius at least ?
Solution:
It is not possible. The proof is by contradiction. Suppose that such a covering family exists. Let denote the disc with center and radius . Start with an arbitrary disc that does not overlap any member of . Then covers no grid point. Take the disc to be maximal in the sense that any further enlargement would cause it to violate the non-overlap condition. Then is tangent to at least three discs in . Observe that there must be two of the three tangent discs, say and , such that . By the Law of Cosines applied to triangle ,
which yields
Note that because covers no grid point, and because each disc in has radius at least 5 . Hence , which gives and thus . Squaring both sides of this inequality yields . This contradiction completes the proof.
Remark: The above argument shows that no covering family exists where each disc has radius greater than . In the other direction, there exists a covering family in which each disc has radius . Take discs with this radius centered at points of the form , where and are integers. Then any grid point is within of one of the centers and the distance between any two centers is at least . The extremal radius of a covering family is unknown.
This problem was suggested by Gregory Galperin.
The problems on this page are the property of the MAA's American Mathematics Competitions