Difference between revisions of "2007 USAMO Problems/Problem 2"

Revision as of 02:34, 7 August 2014

Problem

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

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.

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.

@@ Line 25: / Line 25: @@
 == See also ==
+* <url>viewtopic.php?t=145844 Discussion on AoPS/MathLinks</url>
 {{USAMO newbox|year=2007|num-b=1|num-a=3}}

2007 USAMO (Problems • Resources)
Preceded by Problem 1	Followed by Problem 3
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search