Difference between revisions of "2007 USAMO Problems/Problem 2"
m (solution written by Altheman (2 lazy 2 type up mines), will clean up soon) |
(-> tex, wikify) |
||
Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
− | A square grid on the Euclidean plane consists of all | + | 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? |
== Solution == | == Solution == | ||
− | Lemma: among 3 tangent circles with radius greater than or equal to 5, one can always fit a circle with radius greater than 1 | + | '''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 | + | '''Proof''': [[Descartes' Circle Theorem]] states that if a is the curvature of a circle (<math>a=\frac 1{r}</math>, positive for [[externally tangent]], negative for [[internally tangent]]), then we have that |
− | a | + | <div style='text-align:center;'><math>\displaystyle (a+b+c+d)^2=2(a^2+b^2+c^2+d^2)</math></div> |
− | + | Solving for a, we get | |
− | |||
− | |||
− | 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 | + | <div style='text-align:center;'><math>a=b+c+d+2 \sqrt{bc+cd+db}</math></div> |
+ | |||
+ | Take the positive root, as the negative root corresponds to externally tangent circle. | ||
+ | |||
+ | 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]]/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. | ||
+ | |||
+ | ---- | ||
+ | |||
+ | 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. | ||
+ | |||
+ | == See also == | ||
{{USAMO newbox|year=2007|num-b=1|num-a=3}} | {{USAMO newbox|year=2007|num-b=1|num-a=3}} | ||
[[Category:Olympiad Geometry Problems]] | [[Category:Olympiad Geometry Problems]] |
Revision as of 15:40, 26 April 2007
Problem
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?
Solution
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 a is the curvature of a circle (, positive for externally tangent, negative for internally tangent), then we have that
![$\displaystyle (a+b+c+d)^2=2(a^2+b^2+c^2+d^2)$](http://latex.artofproblemsolving.com/c/a/5/ca52c5d7434091d8f03105806dede7e239f36891.png)
Solving for a, we get
![$a=b+c+d+2 \sqrt{bc+cd+db}$](http://latex.artofproblemsolving.com/1/8/3/183b327e7219cc585ddb9f8737fa738816070cc3.png)
Take the positive root, as the negative root corresponds to externally 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.
See also
2007 USAMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |