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 (ProblemsResources)
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. AMC logo.png