Maths Olympiad Prep

Library / USAMO /32 of 156

USAMO

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 ∠AOB≤120∘\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
ab≤3(a+b)r+3r2,and thus12r2≥(a−3r)(b−3r). 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 (a−3r)(b−3r)≥(5−3r)2(a-3r)(b-3r) \ge (5-3r)^2 because each disc in F\mathcal{F} has radius at least 55. Hence 23r≥(5−3r)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+12⋅2=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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.