Maths Olympiad Prep

Library / /35 of 169

Geometry Difficulty 7.0 National Olympiad, round 2 Prove it United States

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 55?

Solution

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 \le 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 \le (a+r)^2 + (b+r)^2 + (a+r)(b+r),
which yields
ab3(a+b)r+3r2,and thus12r2(a3r)(b3r). ab \le 3(a+b)r + 3r^2, \quad \text{and thus}\quad 12r^2 \ge (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) \ge (5-3r)^2 because each disc in F\mathcal{F} has radius at least 55. Hence 23r(53r)2\sqrt{3}r \ge (5-3r), which gives 5(3+23)r<(3+23)/25 \le (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.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.