2007 USAMO Problems/Problem 2
Contents
[hide]Problem
(Gregory Galperin) 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?
Solutions
Solution 1
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 is the curvature of a circle (
, positive for externally tangent, negative for internally tangent), then we have that
Solving for
, we get
Take the positive root, as the negative root corresponds to internally 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.
Solution 2
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
and thus
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 with
of one of the centers and the distance between any two centers is at least
. The extremal radius of a covering family is unknown.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
See also
- <url>viewtopic.php?t=145844 Discussion on AoPS/MathLinks</url>
2007 USAMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.