PigeonholePrinciple ColoringMethod IMO Intermediate
1964


Problem - 2749
Seventeen people correspond by mail with one another - each one with all the rest. In their letters only three different topics are discussed. Each pair of correspondents deals with only one of these topics. Prove that there are at least three people who write to each other about the same topic.

This is an extension to # 2747 and can be solved in a similar way.

We can model these $17$ people using $17$ points and the $3$ languages using $3$ different colored edges connecting these points. Then the to-be-proved claim is equivalent to show that there must exist a triangle made up with same colored edges.

Pick up any point, there will be $16$ edges starting from this point. By the pigeonhole principle, at least $6$ of them will share the same color. Then if any two of these $6$ points are connected by the same color, the conclusion will hold.

Otherwise, if no points among these $6$ are connected by this color, they must be connected by one of the rest two colors. In this case, this problem becomes # 2747, i.e. if $6$ points are connected using two colors, there must exist a triangle whose edges are of the same color. We know, it is true.

Hence, the original claim hold.

report an error