Maths Olympiad Prep

Library / /8 of 19

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Germany

Problem:
In the plane there are nn closed disks K1,K2,,KnK_{1}, K_{2}, \ldots, K_{n} with equal radius rr. Every point of the plane is contained in at most 20032003 of these disks. Prove that every disk KiK_{i} intersects at most 1402014020 other disks.

Solution

Solution:
We give a proof by contradiction. In addition to the hypothesis, we assume that a disk (without loss of generality let this be K1K_{1}) intersects at least 1402114021 other disks. The centers of these disks then obviously all lie in a disk of radius 2r2r about the center M1M_{1} of K1K_{1}. If 20032003 or more of the centers of these other disks were to lie in or on the boundary of K1K_{1}, then all these disks would contain M1M_{1}. Then M1M_{1} would be contained in more than 20032003 disks, since M1M_{1} is also contained in K1K_{1}. Hence at least 140212002=1201914021 - 2002 = 12019 centers of the other disks must lie in an annulus with inner radius rr and outer radius 2r2r about M1M_{1}. If we divide this annulus into 66 equally sized sectors with interior angle 6060^{\circ}, then by the pigeonhole principle at least one sector contains at least 20042004 of these centers.
In the diagram this sector is shown with the midpoint MM of the segment ABAB. From AM1=BM1=2r|AM_{1}| = |BM_{1}| = 2r and AM1B=60\angle AM_{1}B = 60^{\circ} it follows that ABM1\triangle ABM_{1} is equilateral. Hence MDMD and MCMC are its midlines, and it follows that MA=MB=MC=MD=r|MA| = |MB| = |MC| = |MD| = r. Therefore the sector lies entirely within a circle about MM with radius rr. Each of the at least 20042004 disks with centers in this sector therefore contains the point MM. Thus MM is contained in
Figure 1
at least 20042004 disks — a contradiction to the assumption.

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 translated into English from de; metadata (topic, difficulty) added by this project.