France Olympiad Team Selection Test 2005

Question

In an international meeting of $n ≥ 3$ participants, $14$ languages are spoken. We know that: - Any $3$ participants speak a common language. - No language is spoken by more than half of the participants. What is the least value of $n$?

Answer 1

$n ≥ 3$ participants, 14 languages are spoken. We know that: - Any $3$ participants speak a common language. - No language is spoken by more than $\frac{1}{2}$ of the participants. What is the least value of $n$?

The numbers, $(14,3,\leq 1/2)$, can be understood from geometry over finite fields.

They are suspiciously close to the case of $15 = q^3 + q^2 + q + 1$ languages ($q=2$), which is the number of points in a $3$ dimensional projective space over finite field of $q$ elements, where each plane goes through at most $1/q$ of the points and (dually) every point is on at most $1/q$ of the planes [more exactly, (number of points) $=1 + q \times$ (number of planes)]. If the participants are identitied with planes, the languages with points, and speaking a language with containing a point, this almost matches the numbers in the problem, but there is an extra point.

Since finite field configurations tend to be extremal, the $15$ pattern is probably some sort of efficient extension of the solution to this problem. Indeed, the $14$ languages would be explained if one point were removed (so languages=$15-1$) together with all planes through that point (reducing participants to $q^3=8$). This construction has the same numbers as stated to be optimal in Calvin Lin's answer.

The generalizations of the question seem to be related to Steiner systems.

Answer 2

Set up the standard incidence matrix.

Let the row be the $n$ participants and the 14 columns be the languages. Fill in the entry of 1 if the participant can speak the language.

We wish to count the number of column triples $\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}$. Since every 3 participants speak a common language, this number is at least $ n \choose 3$. Since every language is spoken by half or less (my interpretation), there is at most $15 \times { \frac{n}{2} \choose 3}$ such triples.

Solving ${ n \choose 3} \leq 14{ \frac{n}{2} \choose 3}$, which is equivalent to $(n-1)(n-8) \geq 0 $, we get $ n \leq 1, n \geq 8 $. Hence, the least possible value of $n$ is 8.

It remains to show that $n=8 $ is possible. This is quite easy to do so, if you remember that equality must hold throughout. Hence, no 3 participants speak 2 common languages, is a necessary and sufficient condition. There is a natural choice, which works.

---

For the first 7 languages, use

$ \begin{array} { | l | l | l | l | l | l | l |} \hline 1&1&1&1&0&0&0 \\ \hline 1&1&0&0&1&1&0 \\ \hline 1&0&1&0&1&0&1 \\ \hline 1&0&0&1&0&1&1 \\ \hline 0&1&1&1&0&0&0 \\ \hline 0&1&0&0&1&1&0 \\ \hline 0&0&1&0&1&0&1 \\ \hline 0&0&0&1&0&1&1 \\ \hline \end{array} $

For the next 7 languages, use 1 minus entries in the above table.