Difference between revisions of "2007 USAMO Problems/Problem 2"
m (solution written by Altheman (2 lazy 2 type up mines), will clean up soon) |
|||
| Line 4: | Line 4: | ||
== 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/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 | ||
| + | |||
| + | a=b+c+d+2*sqrt(bc+cd+db) [take positive root, negative root corresponds to externally tangent circle] | ||
| + | |||
| + | now clearly, we have b+c+d=<3/5, and bc+cd+db=<3/25 | ||
| + | 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 | ||
| + | --- | ||
| + | |||
| + | 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. | ||
{{USAMO newbox|year=2007|num-b=1|num-a=3}} | {{USAMO newbox|year=2007|num-b=1|num-a=3}} | ||
| + | |||
| + | [[Category:Olympiad Geometry Problems]] | ||
Revision as of 18:35, 25 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 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
a=b+c+d+2*sqrt(bc+cd+db) [take positive root, negative root corresponds to externally tangent circle]
now clearly, we have b+c+d=<3/5, and bc+cd+db=<3/25 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 ---
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.
| 2007 USAMO (Problems • Resources) | ||
| Preceded by Problem 1 |
Followed by Problem 3 | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAMO Problems and Solutions | ||
