Maths Olympiad Prep

Track / Stage 6 / 247 of 400 #1247 of 1964

Problem 1247

National Olympiad, first round
Combinatorics Difficulty 6.3 Prove it

In a plane of height 285, there are 12 circles. If any three circles have at least two circles that are disjoint, prove: there must be four circles among the 12 circles that are pairwise disjoint.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Prove (1) Take any six circles, and represent the six circles with six points.

If two circles are disjoint, connect them with a red line; if two circles are not disjoint, connect them with a blue line. It is easy to know that six points connected with two colors must contain a monochromatic triangle.

Given that there is no blue triangle, there must be a red triangle, i.e., among the six circles, there must be three circles that are pairwise disjoint.
(2) Let ⊙A\odot A be the circle with the smallest radius among 12 circles. It can be proven: The number of circles not disjoint from ⊙A\odot A is at most five.
If not, ⊙A\odot A is not disjoint from ⊙A1,⊙A2,⋯ ,⊙A6\odot A_{1}, \odot A_{2}, \cdots, \odot A_{6}.
Suppose one of ⊙Ai(i=1,2,⋯ ,6)\odot A_{i}(i=1,2, \cdots, 6) is concentric with ⊙A\odot A, without loss of generality, let ⊙A1\odot A_{1} be concentric with ⊙A\odot A. Then, since ⊙A2\odot A_{2} is not disjoint from ⊙A\odot A, and the radius of ⊙A1\odot A_{1} is greater than the radius of ⊙A\odot A, hence ⊙A,⊙A1,⊙A2\odot A, \odot A_{1}, \odot A_{2} are mutually not disjoint, which is a contradiction.
Thus, ⊙Ai\odot A_{i} are not concentric with ⊙A\odot A.
Let the points A1A_{1}, A2,⋯ ,A6A_{2}, \cdots, A_{6} be arranged in a counterclockwise direction around point AA. Since
∠A1AA2+∠A2AA3+∠A3AA4+∠A4AA5+∠A5AA6+∠A6AA1=2π, \begin{array}{l} \angle A_{1} A A_{2}+\angle A_{2} A A_{3}+\angle A_{3} A A_{4}+ \\ \angle A_{4} A A_{5}+\angle A_{5} A A_{6}+\angle A_{6} A A_{1}=2 \pi, \end{array}

there must be one of the six angles that is no greater than π3\frac{\pi}{3}.
Without loss of generality, let ∠A1AA2⩽π3\angle A_{1} A A_{2} \leqslant \frac{\pi}{3}. Then
A1A2⩽max⁡{A1A,AA2}.  A_{1} A_{2} \leqslant \max \left\{A_{1} A, A A_{2}\right\} \text {. }

Since ⊙A\odot A is not disjoint from ⊙A1\odot A_{1} and ⊙A2\odot A_{2}, then ⊙A1\odot A_{1} and ⊙A2\odot A_{2} are disjoint. Therefore,
rA1+rA2<A1A2⩽max⁡{AA1,AA2}⩽max⁡{rA+rA1,rA+rA2}, \begin{array}{l} r_{A_{1}}+r_{A_{2}}<A_{1} A_{2} \leqslant \max \left\{A A_{1}, A A_{2}\right\} \\ \leqslant \max \left\{r_{A}+r_{A_{1}}, r_{A}+r_{A_{2}}\right\}, \end{array}

where rA1r_{A_{1}} represents the radius of ⊙Ai\odot A_{i}.
Without loss of generality, let rA1+rA2<rA1+rA1r_{A_{1}}+r_{A_{2}}<r_{A_{1}}+r_{A_{1}}. Then rA2<rAr_{A_{2}}<r_{A}, which contradicts the fact that ⊙A\odot A is the circle with the smallest radius among the 12 circles.
Thus, the number of circles not disjoint from ⊙A\odot A is at most five.
Therefore, among the 12 circles, there are at least six circles that are disjoint from ⊙A\odot A.

By (1), among the six circles disjoint from ⊙A\odot A, there must be three circles that are pairwise disjoint. Adding ⊙A\odot A to these three circles, there are four circles that are pairwise disjoint.
Thus, the problem is proven.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.