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