Maths Olympiad Prep

Track / Stage 6 / 192 of 400 #1192 of 1964

Problem 1192

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.

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
A1A2max{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<A1A2max{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 and solution reproduced as published; topic, difficulty and ordering added by this site.