Solution to September 2002 Problem

Each person in a group of seven people speaks at most two languages, while among every three of them there are at least two who can communicate. Prove that there are three people who speak a common language.

Solution:
We received solutions from Pierre Bornsztein (France), Normand Laliberté (Ontario), Patrick J. LoPresti (Massachusetts), Juan Mir Pieras (Spain) and Alexander Potapenko (Russia). According to our records, Bornsztein and LalibertŽ speak French and English, LoPresti speaks English, Mir speaks Spanish and English, and Potapenko speaks Russian and English. Note that all five respondents can communicate in English. Xing Chiu (Ontario) noted that if people spoke English as their second language, then everybody could communicate with one another!

However, when there is no common language, many things are possible. Consider three friends who meet at a café in Madrid:

A speaks Arabic and Basque,
B speaks Basque and Catalan, and
C speaks Catalan and Arabic. Certainly any pair of them can converse using their common language, but there exists no language common to all three. A similar situation arises for the three friends, D, E, and F, who meet at a café in Prague: D speaks English and German,
E speaks German and Russian, and
F speaks Russian and English. What happens when all six, A, B, C, D, E, and F, meet? Note that for any three of them, you can find two who speak a common language. However there is no language spoken by three or more of them. The September problem calls for proving that this situation cannot occur in any group of seven.

All five of the solutions we received are based on the simple observation that

If a person can communicate with at least three other people,    (*)
then there exists three who speak the same language. Indeed, if Amandine, who speaks only French and Spanish, can communicate with Pierre, Leticia, and Juan, then at least two of these three can speak French, or two of them (say, Leticia and Juan) can speak Spanish. This means that Amandine, Leticia, and Juan can all speak Spanish.

With the help of this observation LoPresti, Mir, and Potapenko solved our problem as follows: Pick one of the seven; let's call her Eve. If she could communicate with at least three people, then three people speak a common language as a consequence of (*). The only other possibility is that Eve communicates with at most two. That would leave at least four who cannot communicate with Eve. Each pair of these four can communicate, because should two of them not have a common language they would form with Eve a threesome with no common language, contrary to the initial assumptions. Thus each of those unable to talk with Eve can communicate with at least three others, and the conclusion we seek -- that there is a language common to at least three people -- follows again from observation (*).

Laliberté's solution makes use of the pigeon-hole principle. Let us examine again the case where Eve can communicate with at most two people. Choose one of those people, say Lilith, who cannot talk with Eve. Then Eve and Lilith together speak at most four languages. All of the other five people must speak at least one of these four languages -- otherwise they would each form with Eve and Lilith a threesome with no common language. Thus, one of the four languages is spoken by at least two of the five, in addition to being spoken by either Eve or Lilith. Thus, this language is spoken by at least three, as desired.

Finally, Bornsztein's solution is based on Turan's theorem. Consider the graph whose vertices represent the seven people, and whose edges join two people who cannot communicate. According to our hypotheses, this graph contains no triangles -- that is, no triples (A, B, C} of vertices for which every pair is joined by an edge. Turan's theorem says that a triangle-free graph with n vertices has at most edges. Here, with n = 7, there can be at most 12 edges (the largest whole number less than  49/4). Since seven vertices form  7x6/2 = 21 pairs, there remain at least 21 - 12 = 9 pairs with no connecting edge (corresponding to pairs of people having a common language). Denote by d(i) the number of people having a common language with the ith person. The average of these numbers d(i) is

Each pair {i, j} with a common language contributes two to the numerator -- one for d(i) and one for d(j). Thus the above average equals 2*(the number of pairs with a common language)/7. This is at least  2x9/7 which is approximately 2.57. Consequently, at least one of the d(i) >= 2.57; since d(i) is an integer, it must be at least 3. It follows that the ith person can communicate with at least three other people, and therefore, from observation (*) we again see that there must be a language common to at least three people.

Further comment. Let N(t, m, p) denote the largest number of people where (1) each speaks at most t languages; (2) among any m, two speak a common language; and (3) no p speak a common language. H.L. Abbott, D. Hanson, and A.C. Liu investigated this number in "An Extremal Problem in Graph Theory," Quarterly Journal of Mathematics 31:121 (March, 1980), pages 1-7. Our problem calls for showing that N(2,3,3) < 7.