Maths Olympiad Prep

Library / /55 of 115

Geometry Difficulty 7.3 National olympiad, round 2 Find the answer

( Gregory Galperin ) A square grid on the Euclidean plane consists of all points (m,n)(m,n) , where mm and nn 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 number or a short expression. Spacing and $ signs are ignored.

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 12\frac{1}{\sqrt{2}} between those 3 circles.
Proof. Descartes' Circle Theorem states that if aa is the curvature of a circle ( a=1ra=\frac 1{r} , positive for externally tangent , negative for internally tangent ), then we have that (a+b+c+d)2=2(a2+b2+c2+d2)(a+b+c+d)^2=2(a^2+b^2+c^2+d^2) Solving for aa , we get a=b+c+d+2bc+cd+dba=b+c+d+2 \sqrt{bc+cd+db} Take the positive root, as the negative root corresponds to internally tangent circle.
Now clearly, we have b+c+d35b+c+d \le \frac 35 , and bc+cd+db325bc+cd+db\le \frac 3{25} .
Summing/ square root /multiplying appropriately shows that a3+235a \le \frac{3 + 2 \sqrt{3}}5 . Incidently, 3+235<2\frac{3 + 2\sqrt{3}}5 < \sqrt{2} , so a<2a< \sqrt{2} , r>12r > \frac 1{\sqrt{2}} , as desired. \blacksquare
For sake of contradiction , assume that we have a satisfactory placement of circles. Consider 3 circles, p, q, rp,\ q,\ r where there are no circles in between. By Appolonius' problem , there exists a circle tt tangent to p, q, rp,\ q,\ r externally that is between those 3 circles. Clearly, if we move p, q, rp,\ q,\ r together, tt 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 12\frac{1}{\sqrt{2}} that lies between p, q, rp,\ q,\ r . However, any circle with r>12r>\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.
Solution 2
It is not possible. The proof is by contradiction. Suppose that such a covering family F\mathcal{F} exists. Let D(P,ρ)D(P,\rho) denote the disc with center PP and radius ρ\rho . Start with an arbitrary disc D(O,r)D(O,r) that does not overlap any member of F\mathcal{F} . Then D(O,r)D(O,r) covers no grid point. Take the disc D(O,r)D(O,r) to be maximal in the sense that any further enlargement would cause it to violate the non-overlap condition. Then D(O,r)D(O,r) is tangent to at least three discs in F\mathcal{F} . Observe that there must be two of the three tangent discs, say D(A,a)D(A,a) and D(B,b)D(B,b) such that AOB120\angle AOB\leq 120^\circ . By the Law of Cosines applied to triangle ABOABO , (a+b)2(a+r)2+(b+r)2+(a+r)(b+r),(a + b)^2\leq (a + r)^2 + (b + r)^2 + (a + r)(b + r), which yields ab3(a+b)r+3r2,ab\leq 3(a + b)r + 3r^2, and thus 12r2(a3r)(b3r).12r^2\geq (a - 3r)(b - 3r). Note that r<1/2r < 1/\sqrt{2} because D(O,r)D(O,r) covers no grid point, and (a3r)(b3r)(53r)2(a - 3r)(b - 3r)\geq (5 - 3r)^2 because each disc in F\mathcal{F} has radius at least 5. Hence 23r53r2\sqrt{3}r\geq 5 - 3r , which gives 5(3+23)r<(3+23)/25\leq (3 + 2\sqrt{3})r < (3 + 2\sqrt{3})/\sqrt{2} and thus 52<3+235\sqrt{2} < 3 + 2\sqrt{3} . Squaring both sides of this inequality yields 50<21+123<21+122=4550 < 21 + 12\sqrt{3} < 21 + 12\cdot 2 = 45 . This contradiction completes the proof.
Remark: The above argument shows that no covering family exists where each disc has radius greater than (3+23)/24.571(3 + 2\sqrt{3})/\sqrt{2}\approx 4.571 . In the other direction, there exists a covering family in which each disc has radius 13/21.802\sqrt{13}/2\approx 1.802 . Take discs with this radius centered at points of the form (2m+4n+12,3m+12)\left(2m + 4n + \frac{1}{2}, 3m + \frac{1}{2}\right) , where mm and nn are integers. Then any grid point is with 13/2\sqrt{13}/2 of one of the centers and the distance between any two centers is at least 13\sqrt{13} . The extremal radius of a covering family is unknown.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.