# France Olympiad Team Selection Test 2005

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$?

$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.

• that's (number of points in the 3d projective space) = 1 + q(number of planes on a point in the 3d space). But the dual to omitting a point and all hyperplanes through it is to omit the hyperplane at infinity and all points on it, so that this can also be described as affine 3-space, with participants the q^3 points and languages the q^3+q^2+q affine planes, each containing q^2 points. – zyx Nov 9 '13 at 21:23

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.

• @zyx I didn't relate it to projective planes (which would have been my next attempt), as my first choice worked. I'd add it in. – Calvin Lin Nov 8 '13 at 23:59
• Thanks for the edit explaining the construction. For the optimal parameters with 4 participants per language it is a S(3,4,14) Steiner quadruple system and according to mathworld.wolfram.com/SteinerQuadrupleSystem.html there are 4 nonisomorphic solutions. – zyx Nov 9 '13 at 3:39