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 non-overlapping 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 . Hence , which gives and thus . Squaring both sides of this inequality yields . This contradiction completes the proof.