2007 USAMO Problems/Problem 2


(Gregory Galperin) A square grid on the Euclidean plane consists of all points $(m,n)$, where $m$ and $n$ 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 1

Lemma. Among 3 tangent circles with radius greater than or equal to 5, one can always fit a circle with radius greater than $\frac{1}{\sqrt{2}}$ between those 3 circles.

Proof. Descartes' Circle Theorem states that if $a$ is the curvature of a circle ($a=\frac 1{r}$, positive for externally tangent, negative for internally tangent), then we have that \[(a+b+c+d)^2=2(a^2+b^2+c^2+d^2)\] Solving for $a$, we get \[a=b+c+d+2 \sqrt{bc+cd+db}\] Take the positive root, as the negative root corresponds to internally tangent circle.

Now clearly, we have $b+c+d \le \frac 35$, and $bc+cd+db\le \frac 3{25}$. Summing/square root/multiplying appropriately shows that $a \le \frac{3 + 2 \sqrt{3}}5$. Incidently, $\frac{3 + 2\sqrt{3}}5 < \sqrt{2}$, so $a< \sqrt{2}$, $r > \frac 1{\sqrt{2}}$, as desired. $\blacksquare$

For sake of contradiction, assume that we have a satisfactory placement of circles. Consider 3 circles, $p,\ q,\ r$ where there are no circles in between. By Appolonius' problem, there exists a circle $t$ tangent to $p,\ q,\ r$ externally that is between those 3 circles. Clearly, if we move $p,\ q,\ r$ together, $t$ 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 $\frac{1}{\sqrt{2}}$ that lies between $p,\ q,\ r$. However, any circle with $r>\frac 1{\sqrt{2}}$ 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 $\mathcal{F}$ exists. Let $D(P,\rho)$ denote the disc with center $P$ and radius $\rho$. Start with an arbitrary disc $D(O,r)$ that does not overlap any member of $\mathcal{F}$. Then $D(O,r)$ covers no grid point. Take the disc $D(O,r)$ to be maximal in the sense that any further enlargement would cause it to violate the non-overlap condition. Then $D(O,r)$ is tangent to at least three discs in $\mathcal{F}$. Observe that there must be two of the three tangent discs, say $D(A,a)$ and $D(B,b)$ such that $\angle AOB\leq 120^\circ$. By the Law of Cosines applied to triangle $ABO$, \[(a + b)^2\leq (a + r)^2 + (b + r)^2 + (a + r)(b + r),\] which yields \[ab\leq 3(a + b)r + 3r^2,\] and thus \[12r^2\geq (a - 3r)(b - 3r).\] Note that $r < 1/\sqrt{2}$ because $D(O,r)$ covers no grid point, and $(a - 3r)(b - 3r)\geq (5 - 3r)^2$ because each disc in $\mathcal{F}$ has radius at least 5. Hence $2\sqrt{3}r\geq 5 - 3r$, which gives $5\leq (3 + 2\sqrt{3})r < (3 + 2\sqrt{3})/\sqrt{2}$ and thus $5\sqrt{2} < 3 + 2\sqrt{3}$. Squaring both sides of this inequality yields $50 < 21 + 12\sqrt{3} < 21 + 12\cdot 2 = 45$. This contradiction completes the proof.

Remark: The above argument shows that no covering family exists where each disc has radius greater than $(3 + 2\sqrt{3})/\sqrt{2}\approx 4.571$. In the other direction, there exists a covering family in which each disc has radius $\sqrt{13}/2\approx 1.802$. Take discs with this radius centered at points of the form $\left(2m + 4n + \frac{1}{2}, 3m + \frac{1}{2}\right)$, where $m$ and $n$ are integers. Then any grid point is with $\sqrt{13}/2$ of one of the centers and the distance between any two centers is at least $\sqrt{13}$. 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 (ProblemsResources)
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. AMC logo.png


Stay Connected

Subscribe to get news and
updates from AoPS, or Contact Us.
© 2015
AoPS Incorporated
Invalid username
Login to AoPS