CombinatoricsDifficulty 6.2National olympiadProve it
(15) Given that P1,P2,P3,⋯,P35 are the 35 vertices of a convex 35-sided polygon in a plane, and the distance between any two points among P1,P2,P3,⋯,P35 is no less than 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 P be any one of the 35 points P1,P2,P3,⋯,P35. Then, among the remaining 34 points, at most 6 points are less than 3 units away from P. (Proof by contradiction) Suppose there are 7 points, say P1,P2,P3,⋯,P7 (arranged counterclockwise), that are less than 3 units away from point P.
Since P1,P2,P3,⋯,P35 are the 35 vertices of a convex 35-sided polygon, we have ∠P1PP2+∠P2PP3+∠P3PP4+∠P4PP5+∠P5PP6+∠P6PP7⩽180∘.
Therefore, among the 6 angles ∠P1PP2,∠P2PP3,∠P3PP4,∠P4PP5,∠P5PP6,∠P6PP7, at least one angle is no greater than 30∘. Without loss of generality, let ∠P1PP2⩽30∘. Let PP1=x,PP2=y, then P1P22=x2+y2−2xycos∠P1PP2⩽x2+y2−2xycos30∘=x2+y2−3xy.
By symmetry, assume x⩾y. Since 3⩽y⩽x<3, we have P1P22=f(x)=x2+y2−3xy=(x−23y)2+41y2
is an increasing function on the interval [y,3). Therefore, P1P22=f(x)<f(3)=9+y2−33y=(y−233)2+49⩽(3−233)2+43=3,
Thus, P1P2<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,⋯,P1P35 starting from P1, 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,⋯,P1P29 have a length not less than 3.
Next, consider the 27 segments P2P3,P2P4,P2P5,⋯,P2P29 starting from P2. 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,⋯,P2P23 have a length not less than 3.
Next, consider the 20 segments P3P4,P3P5,P3P6,⋯,P2P23 starting from P3. 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,⋯,P3P17 have a length not less than 3.
Next, consider the 13 segments P4P5,P4P6,P4P7,⋯,P4P17 starting from P4. 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,⋯,P4P11 have a length not less than 3.
Thus, we have 5 points P1,P2,P3,P4,P5. 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.