
4. There are 100 countries participating in an olympiad. Suppose $n$ is a positive integer such that each of the 100 countries is willing to communicate in exactly $n$ languages. If each set of 20 countries can communicate in at least one common language, and no language is common to all 100 countries, what is the minimum possible value of $n$ ?


Solution: We show that $n=20$. We first show that $n=20$ is possible. Call the countries $C_{1}, \cdots, C_{100}$. Let $1,2, \cdots, 21$ be languages and suppose, the country $C_{i}(1 \leq i \leq 20)$ communicates exactly in the languages $\{j: 1 \leq j \leq 20, j \neq i\}$. Suppose each of the countries $C_{21}, \cdots, C_{100}$ communicates in the languages $1,2, \cdots, 20$. Then, clearly every set of 20 countries have a common language of communication.

Now, we show that $n \geq 20$. If $n<20$, look at any country $A$ communicating in the languages $L_{1}, \cdots, L_{n}$. As no language is common to all 100 countries, for each $L_{i}$, there is a country $A_{i}$ not communicating in $L_{i}$. Then, the $n+1 \leq 20$ countries $A, A_{1}, A_{2}, \cdots, A_{n}$ have no common language of communication. This contradiction shows $n \geq 20$.
