A problem from the Sixth International Mathematical Olympiad, 1964: Seventeen people correspond by mail, each with all the rest. They discuss only three topics, and each pair of correspondents addresses only one of these. Prove that there are at least three people who write to each other about the same topic.
|
SelectClick for Answer |
Choose one person and call her A. She corresponds with 16 other people, and since there are only three topics, she must correspond with at least six people about some one of these topics.
Call that Topic 1. Now if any of her correspondents on that topic writes to another about the same subject, then we’ve found three people who are corresponding about the same topic. So assume that A’s six correspondents write to one another only about Topics 2 and 3.
But now consider one of these six people; call her B. She is corresponding with the other five and addressing only two topics with them. That means that she must be addressing some particular topic with at least three of the five. Call that Topic 2.
Now consider those three people. If one of the three writes to another about Topic 2, then we’ve found three people writing to each other about the same topic. And if none of the three writes to another about Topic 2, then all three of them must write to one another about Topic 3, and that proves the assertion.
|
