Maths Olympiad Prep

Library / /465 of 520

Combinatorics Difficulty 6.2 National olympiad Prove it

(15) Given that P1,P2,P3,,P35P_{1}, P_{2}, P_{3}, \cdots, P_{35} are the 35 vertices of a convex 35-sided polygon in a plane, and the distance between any two points among P1,P2,P3,,P35P_{1}, P_{2}, P_{3}, \cdots, P_{35} is no less than 3\sqrt{3}. Prove that: from these 35 points, 5 points can be selected such that the distance between any two of these 5 points is no less than 3.

Solution

15 First prove the following lemma: Let PP be any one of the 35 points P1,P2,P3,,P35P_{1}, P_{2}, P_{3}, \cdots, P_{35}. Then, among the remaining 34 points, at most 6 points are less than 3 units away from PP.
(Proof by contradiction) Suppose there are 7 points, say P1,P2,P3,,P7P_{1}, P_{2}, P_{3}, \cdots, P_{7} (arranged counterclockwise), that are less than 3 units away from point PP.

Since P1,P2,P3,,P35P_{1}, P_{2}, P_{3}, \cdots, P_{35} are the 35 vertices of a convex 35-sided polygon, we have
P1PP2+P2PP3+P3PP4+P4PP5+P5PP6+P6PP7180. \begin{array}{c} \angle P_{1} P P_{2}+\angle P_{2} P P_{3}+\angle P_{3} P P_{4}+\angle P_{4} P P_{5}+ \\ \angle P_{5} P P_{6}+\angle P_{6} P P_{7} \leqslant 180^{\circ} . \end{array}

Therefore, among the 6 angles P1PP2,P2PP3,P3PP4,P4PP5,P5PP6,P6PP7\angle P_{1} P P_{2}, \angle P_{2} P P_{3}, \angle P_{3} P P_{4}, \angle P_{4} P P_{5}, \angle P_{5} P P_{6}, \angle P_{6} P P_{7}, at least one angle is no greater than 3030^{\circ}. Without loss of generality, let P1PP230\angle P_{1} P P_{2} \leqslant 30^{\circ}. Let PP1=x,PP2=yP P_{1}=x, P P_{2}=y, then
P1P22=x2+y22xycosP1PP2x2+y22xycos30=x2+y23xy. \begin{aligned} P_{1} P_{2}^{2} & =x^{2}+y^{2}-2 x y \cos \angle P_{1} P P_{2} \\ & \leqslant x^{2}+y^{2}-2 x y \cos 30^{\circ} \\ & =x^{2}+y^{2}-\sqrt{3} x y . \end{aligned}

By symmetry, assume xyx \geqslant y. Since 3yx<3\sqrt{3} \leqslant y \leqslant x<3, we have
P1P22=f(x)=x2+y23xy=(x32y)2+14y2 P_{1} P_{2}^{2}=f(x)=x^{2}+y^{2}-\sqrt{3} x y=\left(x-\frac{\sqrt{3}}{2} y\right)^{2}+\frac{1}{4} y^{2}

is an increasing function on the interval [y,3)[y, 3). Therefore,
P1P22=f(x)<f(3)=9+y233y=(y332)2+94(3332)2+34=3, \begin{aligned} P_{1} P_{2}^{2} & =f(x)<f(3) \\ & =9+y^{2}-3 \sqrt{3} y \\ & =\left(y-\frac{3 \sqrt{3}}{2}\right)^{2}+\frac{9}{4} \\ & \leqslant\left(\sqrt{3}-\frac{3 \sqrt{3}}{2}\right)^{2}+\frac{3}{4} \\ & =3, \end{aligned}

Thus, P1P2<3P_{1} P_{2}<\sqrt{3}, which contradicts the given condition. Therefore, the assumption is false.
Hence, the lemma is proved.
Now, using the lemma to prove the conclusion of the problem.
According to the lemma, among the 34 segments P1P2,P1P3,P1P4,,P1P35P_{1} P_{2}, P_{1} P_{3}, P_{1} P_{4}, \cdots, P_{1} P_{35} starting from P1P_{1}, at most 6 segments have a length less than 3, i.e., at least 28 segments have a length not less than 3. Without loss of generality, assume the segments P1P2,P1P3,P1P4,,P1P29P_{1} P_{2}, P_{1} P_{3}, P_{1} P_{4}, \cdots, P_{1} P_{29} have a length not less than 3.

Next, consider the 27 segments P2P3,P2P4,P2P5,,P2P29P_{2} P_{3}, P_{2} P_{4}, P_{2} P_{5}, \cdots, P_{2} P_{29} starting from P2P_{2}. According to the lemma, at most 6 of these 27 segments have a length less than 3, i.e., at least 21 segments have a length not less than 3. Without loss of generality, assume the segments P2P3,P2P4,P2P5,,P2P23P_{2} P_{3}, P_{2} P_{4}, P_{2} P_{5}, \cdots, P_{2} P_{23} have a length not less than 3.

Next, consider the 20 segments P3P4,P3P5,P3P6,,P2P23P_{3} P_{4}, P_{3} P_{5}, P_{3} P_{6}, \cdots, P_{2} P_{23} starting from P3P_{3}. According to the lemma, at most 6 of these 20 segments have a length less than 3, i.e., at least 14 segments have a length not less than 3. Without loss of generality, assume the segments P3P4,P3P5,P3P6,,P3P17P_{3} P_{4}, P_{3} P_{5}, P_{3} P_{6}, \cdots, P_{3} P_{17} have a length not less than 3.

Next, consider the 13 segments P4P5,P4P6,P4P7,,P4P17P_{4} P_{5}, P_{4} P_{6}, P_{4} P_{7}, \cdots, P_{4} P_{17} starting from P4P_{4}. According to the lemma, at most 6 of these 13 segments have a length less than 3, i.e., at least 7 segments have a length not less than 3. Without loss of generality, assume the segments P4P5,P4P6,P4P7,,P4P11P_{4} P_{5}, P_{4} P_{6}, P_{4} P_{7}, \cdots, P_{4} P_{11} have a length not less than 3.

Thus, we have 5 points P1,P2,P3,P4,P5P_{1}, P_{2}, P_{3}, P_{4}, P_{5}. According to the previous discussion, the distance between any two of these 5 points is not less than 3.
Therefore, the conclusion holds.

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.