Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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 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?
+
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/sqrt 2 between those 3 circles.  
+
'''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.  
−
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
+
'''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=b+c+d+2*sqrt(bc+cd+db) [take positive root, negative root corresponds to externally tangent circle]
+
<div style='text-align:center;'><math>\displaystyle (a+b+c+d)^2=2(a^2+b^2+c^2+d^2)</math></div>
  
−
now clearly, we have b+c+d=<3/5, and bc+cd+db=<3/25
+
Solving for a, we get
−
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.
+
<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 14:40, 26 April 2007

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

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

$\displaystyle (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 externally 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.

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_USAMO_Problems/Problem_2&oldid=14736"