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

Latest revision as of 03:41, 7 August 2014

Problem

(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?

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 $\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.

@@ Line 1: / Line 1: @@
 == Problem ==
+(''Gregory Galperin'') A [[square]] grid on the [[Cartesian plane|Euclidean plane]] consists of all [[point]]s <math>(m,n)</math>, where <math>m</math> and <math>n</math> are [[integer]]s.  Is it possible to cover all grid points by an infinite family of [[circle|discs]] with non-overlapping interiors if each disc in the family has [[radius]] at least 5?
-A square grid on the Euclidean plane consists of all points <math>(m,n)</math>, where <math>m</math> and <math>n</math> 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 ==
+=== 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 1/sqrt 2 between those 3 circles.
-Proof: descartes' circle theorem states that if a is the curvature of a circle [a=1/radius, 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
+'''Lemma.''' Among 3 [[tangent]] circles with radius greater than or equal to 5, one can always fit a circle with radius greater than <math>\frac{1}{\sqrt{2}}</math> between those 3 circles.
-a=b+c+d+2*sqrt(bc+cd+db) [take positive root, negative root corresponds to externally tangent circle]
+''Proof.'' [[Descartes' Circle Theorem]] states that if <math>a</math> is the curvature of a circle (<math>a=\frac 1{r}</math>, positive for [[externally tangent]], negative for [[internally tangent]]), then we have that
+<cmath>(a+b+c+d)^2=2(a^2+b^2+c^2+d^2)</cmath>
+Solving for <math>a</math>, we get
+<cmath>a=b+c+d+2 \sqrt{bc+cd+db}</cmath>
+Take the positive root, as the negative root corresponds to internally tangent circle.
-now clearly, we have b+c+d=<3/5, and bc+cd+db=<3/25
+Now clearly, we have <math>b+c+d \le \frac 35</math>, and <math>bc+cd+db\le \frac 3{25}</math>.
-summing/square root/multiply appropriately shows that a=<3/5+2*root(3)/5. Incidently, 3/5+2*root(3)/5<root 2, so a<root2, radius>1/root 2, as desired
+Summing/[[square root]]/multiplying appropriately shows that <math>a \le \frac{3 + 2 \sqrt{3}}5</math>. Incidently, <math>\frac{3 + 2\sqrt{3}}5 < \sqrt{2}</math>, so <math>a< \sqrt{2}</math>, <math>r > \frac 1{\sqrt{2}}</math>, as desired. <math>\blacksquare</math>
----
-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 1/root 2 that lies between p,q,r. However, any circle with radius >1/root 2 must contain a lattice point. [Consider placing a circle between a unit square]. That is a contradiction. Hence no tiling exists.
+For sake of [[contradiction]], assume that we have a satisfactory placement of circles. Consider 3 circles, <math>p,\ q,\ r</math> where there are no circles in between. By [[Appolonius' problem]], there exists a circle <math>t</math> tangent to <math>p,\ q,\ r</math> externally that is between those 3 circles. Clearly, if we move <math>p,\ q,\ r</math> together, <math>t</math> 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 <math>\frac{1}{\sqrt{2}}</math> that lies between <math>p,\ q,\ r</math>. However, any circle with <math>r>\frac 1{\sqrt{2}}</math> 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 <math>\mathcal{F}</math> exists. Let <math>D(P,\rho)</math> denote the disc with center <math>P</math> and radius <math>\rho</math>. Start with an arbitrary disc <math>D(O,r)</math> that does not overlap any member of <math>\mathcal{F}</math>. Then <math>D(O,r)</math> covers no grid point. Take the disc <math>D(O,r)</math> to be maximal in the sense that any further enlargement would cause it to violate the non-overlap condition. Then <math>D(O,r)</math> is tangent to at least three discs in <math>\mathcal{F}</math>. Observe that there must be two of the three tangent discs, say <math>D(A,a)</math> and <math>D(B,b)</math> such that <math>\angle AOB\leq 120^\circ</math>. By the Law of Cosines applied to triangle <math>ABO</math>,
+<cmath>(a + b)^2\leq (a + r)^2 + (b + r)^2 + (a + r)(b + r),</cmath>
+which yields
+<cmath>ab\leq 3(a + b)r + 3r^2,</cmath>
+and thus
+<cmath>12r^2\geq (a - 3r)(b - 3r).</cmath>
+Note that <math>r < 1/\sqrt{2}</math> because <math>D(O,r)</math> covers no grid point, and <math>(a - 3r)(b - 3r)\geq (5 - 3r)^2</math> because each disc in <math>\mathcal{F}</math> has radius at least 5. Hence <math>2\sqrt{3}r\geq 5 - 3r</math>, which gives <math>5\leq (3 + 2\sqrt{3})r < (3 + 2\sqrt{3})/\sqrt{2}</math> and thus <math>5\sqrt{2} < 3 + 2\sqrt{3}</math>. Squaring both sides of this inequality yields <math>50 < 21 + 12\sqrt{3} < 21 + 12\cdot 2 = 45</math>. This contradiction completes the proof.
+'''Remark:''' The above argument shows that no covering family exists where each disc has radius greater than <math>(3 + 2\sqrt{3})/\sqrt{2}\approx 4.571</math>. In the other direction, there exists a covering family in which each disc has radius <math>\sqrt{13}/2\approx 1.802</math>. Take discs with this radius centered at points of the form <math>\left(2m + 4n + \frac{1}{2}, 3m + \frac{1}{2}\right)</math>, where <math>m</math> and <math>n</math> are integers. Then any grid point is with <math>\sqrt{13}/2</math> of one of the centers and the distance between any two centers is at least <math>\sqrt{13}</math>. The extremal radius of a covering family is unknown.
+{{alternate solutions}}
+== See also ==
+* <url>viewtopic.php?t=145844 Discussion on AoPS/MathLinks</url>
 {{USAMO newbox|year=2007|num-b=1|num-a=3}}
 [[Category:Olympiad Geometry Problems]]
+{{MAA Notice}}

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