There are 1985 people in a room. Each speaks at most 5 languages. Given any three people, at least two of them have a language in common. Prove that there is a language spoken by at least 200 people in the room.
Solution
Take any person. He speaks at most 5 languages. If everyone in the room speaks at least one of those languages but not more than 199 people speak each language, then there are at most 1 + 5·198 = 991 people in the room. But there are 1985 people, so we must be able to find someone who speaks none of the 5 languages. He too speaks at most 5 languages, giving a total of 10 between the two people selected. Now we are told that every other person speaks at least one of these 10 languages. So if no more than 199 people speak each language, then there are at most 2 + 10·198 = 1982 people in the room. But there are 1985 people, so one of the 10 languages must be spoken by 200 or more people.
© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002