1
$\begingroup$

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

$\endgroup$
0
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – zyx Nov 9 '13 at 21:23
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @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. $\endgroup$ – Calvin Lin Nov 8 '13 at 23:59
  • $\begingroup$ 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. $\endgroup$ – zyx Nov 9 '13 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.