Maths Olympiad Prep

Library / /389 of 520

Geometry Difficulty 7.3 National olympiad, round 2 Prove it

Let F\mathcal{F} be a finite collection of open discs in R2\mathbb{R}^2 whose union contains a set ER2E\subseteq \mathbb{R}^2. Show that there is a pairwise disjoint subcollection D1,,DnD_1,\ldots,D_n in F\mathcal{F} such that Ej=1n3Dj.E\subseteq\cup_{j=1}^n 3D_j. Here, if DD is the disc of radius rr and center PP, then 3D3D is the disc of radius 3r3r and center PP.

Solution

1. Initial Setup: Let F\mathcal{F} be a finite collection of open discs in R2\mathbb{R}^2 whose union contains a set ER2E \subseteq \mathbb{R}^2. We need to find a pairwise disjoint subcollection D1,,DnD_1, \ldots, D_n in F\mathcal{F} such that Ej=1n3DjE \subseteq \bigcup_{j=1}^n 3D_j.

2. Selection Process: We will construct the subcollection D1,,DnD_1, \ldots, D_n iteratively. Start by selecting the largest disc D1D_1 from F\mathcal{F}. Then, for each subsequent disc DiD_i, choose the largest disc from F\mathcal{F} that is disjoint from all previously selected discs D1,,Di1D_1, \ldots, D_{i-1}. This process is possible because F\mathcal{F} is finite, and if multiple discs satisfy the condition, we can choose any one of them arbitrarily.

3. Termination: This selection process will terminate after a finite number of steps because F\mathcal{F} is finite. Let the resulting subcollection be D1,,DnD_1, \ldots, D_n.

4. Proof of Coverage: We need to show that Ej=1n3DjE \subseteq \bigcup_{j=1}^n 3D_j. Consider any disc EkFE_k \in \mathcal{F} that is not in the subcollection D1,,DnD_1, \ldots, D_n. By construction, EkE_k must intersect with at least one of the discs in the subcollection D1,,DnD_1, \ldots, D_n. Let DiD_i be one such disc with which EkE_k intersects.

5. Containment in Enlarged Discs: Since DiD_i was chosen to be the largest disc that is disjoint from the previously selected discs, it follows that the radius of DiD_i is at least as large as the radius of EkE_k. Therefore, the disc 3Di3D_i (which has three times the radius of DiD_i) will completely contain EkE_k.

6. Conclusion: Since every disc EkFE_k \in \mathcal{F} is either in the subcollection D1,,DnD_1, \ldots, D_n or intersects with one of these discs and is contained in the corresponding 3Di3D_i, it follows that the union of the enlarged discs 3D1,,3Dn3D_1, \ldots, 3D_n will cover the entire set EE. Hence, Ej=1n3DjE \subseteq \bigcup_{j=1}^n 3D_j.

\blacksquare

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.