2007 USAMO Problems/Problem 2

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