2007 USAMO Problems/Problem 2
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 non-overlapping interiors if each disc in the family has radius at least 5?
Solution
Lemma: among 3 tangent circles with radius greater than or equal to 5, one can always fit a circle with radius greater than between those 3 circles.
Proof: Descartes' Circle Theorem states that if a is the curvature of a circle (, positive for externally tangent, negative for internally tangent), then we have that

Solving for a, we get

Take the positive root, as the negative root corresponds to externally tangent circle.
Now clearly, we have , and
.
Summing/square root/multiplying appropriately shows that
. Incidently,
, so
,
, as desired.
For sake of contradiction, assume that we have a satisfactory placement of circles. Consider 3 circles, where there are no circles in between. By Appolonius' problem, there exists a circle
tangent to
externally that is between those 3 circles. Clearly, if we move
together,
must decrease in radius. Hence it is sufficient to consider 3 tangent circles. By lemma 1, there is always a circle of radius greater than
that lies between
. However, any circle with
must contain a lattice point. (Consider placing an unit square parallel to the gridlines in the circle.) That is a contradiction. Hence no such tiling exists.
See also
2007 USAMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |