1978 USAMO Problems/Problem 5
Problem
Nine mathematicians meet at an international conference and discover that among any three of them, at least two speak a common language. If each of the mathematicians speak at most three languages, prove that there are at least three of the mathematicians who can speak the same language.
Solution
Suppose no three mathematicians speak the same language. Then person A can share some language with at most 3 other delegates, because if he shared some language with 4 delegates there would be 3 with the same language. So there are 5 delegates who do not share a language with A. Let one of them be B. Using the same logic, one the remaining 4, let it be C, does not share a language with B. Now A, B, C do not have any common languages. Contradiction.
See Also
1978 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Last Question | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.