IMO 1964 · Problem 4

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.

Official text of the problem. Official problem paper (PDF)

Solution

Choose one person \(A\). Of the other sixteen people, at least six correspond with \(A\) about the same topic: otherwise each of the three topics would account for at most five people, giving at most fifteen in total. Call this common topic topic \(1\), and select six such people.

If any two of these six correspond about topic \(1\), they and \(A\) form the required triple. We may therefore assume that every pair among the six corresponds about topic \(2\) or topic \(3\).

Choose one of the six, \(B\). Among the other five, at least three correspond with \(B\) about the same topic, since \(5>2\cdot2\). Denote three such people by \(C,D,E\). Interchanging the names of topics \(2\) and \(3\) if necessary, suppose their correspondence with \(B\) concerns topic \(2\).

If any pair among \(C,D,E\) corresponds about topic \(2\), that pair together with \(B\) forms the required triple. Otherwise all three pairs among \(C,D,E\) correspond about topic \(3\), so \(C,D,E\) themselves form the required triple.

Thus the desired three people exist in every case. \(\square\)

The solution was checked against John Scholes' IMO solution archive (Kalva).