A problem from the second Balkan Mathematical Olympiad, 1985:
Of the 1985 people attending an international meeting, no one speaks more than five languages, and in any subset of three attendees, at least two speak a common language. Prove that some language is spoken by at least 200 of the attendees.
|
SelectClick for Answer> |
If any two of the attendees, A and B, have no language in common, then in any trio that they belong to, the third member, C, must have a language in common with one or both of them. Now suppose that the proposition we’re asked to prove is false — that is, suppose that there are not more than 198 other attendees who speak a language that’s spoken by A or B. A and B know at most 10 languages between them, so at most there are 10 × 198 = 1980 people C who are available to complete an acceptable trio with A and B. But we’ve been told that there are 1985 – 2 = 1983 others who are able to fulfill this role. This is a contradiction, so our supposition, that no language is spoken by 200 attendees, must be false.
“It is easy to forget all about the alternative case, for the odds must be overwhelming that some two of the 1985 participants will be at linguistic loggerheads,” notes Ross Honsberger in From Erdös to Kiev. “However, we still need to consider the possibility that every pair (A, B) have a language in common. Fortunately, this is a trivial case, for then each of the other 1984 people must speak one of the five or fewer languages spoken by A, for an average of at least 397 (counting A).”
|