GMO Combinatorics

[This is not a complete solution. I only show that $n\leq 19$ is not possible, and leave the existence of $n = 20$ to you.]

We will show that $n \leq 19$ is not possible.

Proof by contradiction. Suppose there is a configuration that allows for $n \leq19$ .
Fix one country $C$ , say it speaks $l_1, l_2, \ldots l_{i}$ .
Find a country that does not speak $l_i$ , call it $C_i$ . It is possible that $C_i = C_j$ but that doesn't matter.

Consider any set of 20 countries which have $\{ C, C_1, C_2, \ldots C_n \}$ as a subset. Then, these countries do not have a common language since $C_i$ does not speak $l_i$ and $C$ does not speak any other language.

It remains to find a configuration where $n = 20$ is possible. There are several creative ways of doing this.

Making 5 sets of 100 countries such that there are 20 countries in each set, let the sets be named A, B, C, D, E. All the countries of a set can communicate in n languages, where n>1. We know that there is no language which is common to all sets, therefore to minimize the value of n, all the languages must be common to 4 different sets. 4 sets out of 5 can be chosen as follows:

(A B C D) seak a common language 'P'

(A B C E) speak a common language 'Q'

(A B D E) speak a common language 'R'

(A C D E) speak a common language 'S'

(B C D E) speak a common language 'T'

We see that each set of countries is able to communicate in 4 languages. For eg. Set A communicates in language P, Q, R, S and likewise for set B, C, D, E.

It should be noted that though the total number of languages been spoken in the Olympiad is 5, the minimum possible number of languages that can be spoken by a country in the Olympiad is 4.