Difference between revisions of "2007 USAMO Problems/Problem 2"
(formatting fixes) |
(→Solution) |
||
| Line 22: | Line 22: | ||
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. | 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. | 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. | ||
Revision as of 15:39, 21 March 2012
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
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 
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
Solving for a, we get
Take the positive root, as the negative root corresponds to internally 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 | ||
