Maths Olympiad Prep

Library / Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads /58 of 80

Romania — NMO Selection Tests for the Balkan and International Mathematical Olympiads

Geometry Difficulty 8.4 Shortlist Prove it Romania

Fix a point OO in the plane and an integer n≥3n \ge 3. Consider a finite set D\mathcal{D} of closed unit discs in the plane such that:

(a) No disc in D\mathcal{D} contains the point OO; and

(b) For each positive integer k<nk < n, the closed disc of radius k+1k+1 centred at OO contains the centres of at least kk discs in D\mathcal{D}.

Show that some line through OO stabs at least 2πlog⁡n+12\frac{2}{\pi} \log \frac{n+1}{2} discs in D\mathcal{D}.

Solution

For each disc DD in D\mathcal{D}, let ωD\omega_D denote the centre of DD, and let αD\alpha_D be the arc-length of the image of DD under radial projection from OO onto the unit circle centred at OO. Clearly, αD/2>sin⁡(αD/2)=1/OωD\alpha_D/2 > \sin(\alpha_D/2) = 1/O\omega_D.

Now, for each positive integer k<nk < n, let Dk\mathcal{D}_k be the set of those discs in D\mathcal{D} whose centres lie in the closed disc of radius k+1k+1 centred at OO. Since Di⊆Dj\mathcal{D}_i \subseteq \mathcal{D}_j if i≤ji \le j, and each Dk\mathcal{D}_k contains at least kk elements, we may recursively choose (or apply Hall's marriage theorem to produce) a system of distinct representatives, D1,…,Dn−1D_1, \dots, D_{n-1}, for the collection D1,…,Dn−1\mathcal{D}_1, \dots, \mathcal{D}_{n-1}, to obtain
∑D∈Dn−1αD>2∑D∈Dn−11/OωD≥2∑k=1n−11/OωDk≥2∑k=1n−11/(k+1)>2log⁡n+12. \sum_{D \in \mathcal{D}_{n-1}} \alpha_D > 2 \sum_{D \in \mathcal{D}_{n-1}} 1/O\omega_D \ge 2 \sum_{k=1}^{n-1} 1/O\omega_{D_k} \ge 2 \sum_{k=1}^{n-1} 1/(k+1) > 2 \log \frac{n+1}{2}.
Finally, if Nn−1N_{n-1} is the maximal number of discs in Dn−1\mathcal{D}_{n-1} stabbed by a line through OO as it performs a half-turn about OO, then πNn−1≥∑D∈Dn−1αD\pi N_{n-1} \ge \sum_{D \in \mathcal{D}_{n-1}} \alpha_D and the conclusion follows.

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.