Maths Olympiad Prep

Library / /430 of 520

Combinatorics Difficulty 4.5 AIME Prove it

There are 17 scientists, each of whom communicates with the others, discussing only three topics. In their communications, each pair of scientists discusses only one topic. Prove that there are at least three scientists who communicate with each other on the same topic.

Solution

Proof: Consider one of the 17 points, for example, point A. Draw 16 line segments from point A, which can be colored in three colors. By the pigeonhole principle, there must be at least 6 line segments of the same color, let's say AB, AC, AD, AE, AF, AG are all red.

If among the six points B, C, D, E, F, G, there are two points connected by a red line, suppose these two points are B and C, then ABC\triangle ABC is a triangle with all three sides being red.

If among the six points B, C, D, E, F, G, no two points are connected by a red line, then consider the 5 line segments BC, BD, BE, BF, BG. Their colors can only be two different ones, and there must be 3 line segments of the same color, suppose BC, BD, BE are all yellow. Next, consider the colors of the three sides of CDE\triangle CDE. If they are all blue, then CDE\triangle CDE is a triangle with all three sides being blue. If at least one side is yellow, suppose this side is CD, then BCD\triangle BCD is a triangle with all three sides being yellow. Therefore, there are at least three scientists who communicate with each other on the same topic, which concludes the proof with at least three scientists communicate on the same topic\boxed{\text{at least three scientists communicate on the same topic}}.

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.