There are 9 delegates at a conference, each speaking at most three languages. Given any three delegates, at least 2 speak a common language. Show that there are three delegates with a common language.
Solution
Suppose not. Then A can shares a language with at most 3 delegates, because if he shared a language with 4, he would have to share the same language with 2 of them (since he can only speak 3 languages). So there are 5 delegates who do not share a language with A. Let one of them be B. By the same argument, there must be at least one of the other 4 (call her C) who does not share a language with B. But now no two of A, B, C share a language. Contradiction.
Comment. The result is best possible. Suppose each pair of A, B, C, D share a different language and each pair of A', B', C', D' share a different language (12 languages in total). No other pairs share a language. Then given any three delegates two are primed and share a language or two are unprimed and share a language. But no three delegates share a language.
© John Scholes
jscholes@kalva.demon.co.uk
20 Aug 2002