Journos have a problem!

A problem posed in Nordic Mathematical Contest 1987:


Nine journalists, each from a different country, participate in a press conference. None of them can speak more than three languages, and each two journalists have at least one common language. Prove that at least five of the journalists can speak the same language.


Assume the journalists are J_{1}, J_{2}, J_{3}, \ldots, J_{9}. Assume that no five of them have a common language. Assume the languages J_{1} speaks are L_{1}, L_{2} and L_{3}. Group J_{2}, J_{3}, \ldots, J_{9} according to the language they speak with J_{1}. No group can have more than three members. So, either there are three groups of three members each, or two groups with three members and one with two. Consider the first alternative. We may assume that J_{1} speaks L_{1} with J_{2}, J_{3}, and J_{4}, L_{2} with J_{5}, J_{6}, and J_{7}, and L_{3} with J_{8}, J_{9} and J_{2}. Now, J_{2} speaks L_{1} with J_{1}, J_{3}, and J_{4}, L_{3} with J_{1}, J_{8}, and J_{9}. J_{2} must speak a fourth language, L_{4}, with J_{5}, J_{6}, and J_{7}. But, now J_{5} speaks both L_{2} and L_{4} with J_{2}, J_{6}, and J_{7}. So, J_{5} has to use his third language with J_{1}, J_{4}, J_{8} and J_{9}. This contradicts the assumption we made.

So, we now may assume that J_{1} speaks L_{3} only with J_{8} and J_{9}. As J_{1} is not special, we conclude that for each journalist J_{k}, the remaining eight are divided into three mutually exclusive language groups, one of which has only two members. Now, J_{2} uses L_{1} with three others, and there has to be another language he also speaks with three others. If this were L_{2} or L_{3}, a group of five would arise (including J_{1}). So, J_{2} speaks L_{4} with three among J_{5}, \ldots, J_{9}. Either two of these three are among J_{5}, J_{6}, and J_{7}, or among J_{8}, J_{9}. Both alternatives lead to a contradiction to the already proved fact that no pair of journalists speaks two languages together. Hence, the proof. QED.


Nordic Mathematical Contest, 1987-2009.

Amazon India link:


Nalin Pithwa.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s