1964 IMO Problems/Problem 4

Problem

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.

Solution

Lemma: Consider a complete graph with 6 vertices colored with 2 colors. There exists a monochromatic triangle.

Proof: Consider one vertex and all connections leading out from it. Call it . It has 5 edges coming out from it. By the Pigeonhole Principle, there are at least 3 of the same color. Call this color red. Call those vertices , and . If any of the segments , , or are red, then we have a monochromatic triangle with vertices and the other two that are also red. If they are all the other color, then we have a monochromatic triangle with vertices ,, and .

Main Problem: Represent these people as vertices on a connected graph with 17 vertices and colored with 3 colors, one corresponding with each topic. So this problem is reduced to showing that on a connected graph with 17 vertices and colored with three colors, there exists some monochromatic triangle. Look at an arbitrary vertex. Call it . Look at the 16 other vertices that it is connected to. By the Pigeonhole Principle, there are at least 6 vertices connected to that are all one color. Call this color 1. If any of the connections inbetween these six vertices are in color 1, then we are done. If none of them are color 1, we know that that there are only 2 colors in those 6 vertices. By Lemma 1, we know that there is a monochromatic triangle in those 6 vertices. So we are done.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

1964 IMO (Problems) • Resources
Preceded by Problem 3	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 5
All IMO Problems and Solutions