A conference uses $4$ main languages. Prove that there is a language that at least $\dfrac{3}{5}$ of the delegates know.

Question

A conference uses $4$ main languages. Any two delegates always have a common language that they both know. Prove that there is a language that at least $\dfrac{3}{5}$ of the delegates know.

Source: Romania TST 2002

---

My attempt:

Suppose we have $n$ people and that $l_i$ people speak language $L_i$. We want to prove that $l_i$ is at least $3n/5$ for some $i\in\{1,2,3,4\}$.

Say it is not true. Then we have $l_i<3n/5=:m$ for all $i$. Because of condition we have $$ {n\choose 2} \leq \sum_{i=1}^4{l_i\choose 2} < 4\times {m\choose 2}$$ From here we get $11n>35$ and there is no contradiction if $n>3$.

---

Update (1. 20. 2019): I am now trying to develop the idea that was mentioned by Servaes in the commentary.

Lemma: Among any $4$ delegates there are $3$ that speaks the same languague.

Proof: If somebody speaks only one languague we are done. Say there is somenone that speaks exactly 2 languagues $L_1$ and $L_2$. Then by pigeonhole out of 3 there are two in the same "hole" and we are done again.

Suppose that everyone speaks at least 3 languague. Then by double counting between languagues and 4 people we have $$4\cdot 3\leq 4\cdot l\implies l\geq 3$$ where $l$ is maximum cardinality of $L_i$ in this double counting and we are done. $\square $

Any idea how to finish now?

Answer 1

If somebody speaks only one language, then everybody speaks that language, and we're done. If somebody speaks all four languages, then the desired statement follows by induction after removing that person from the conference. So WLOG suppose everybody speaks two or three languages.

Put the four languages at the vertices of a tetrahedron. If somebody speaks two languages, put them on the edge between the two corresponding vertices, and similarly if they speak three languages put them on the corresponding face. The requirement that everyone have a common language means that two opposite edges cannot be simultaneously occupied. This leaves only two possible topologies for the occupied edges: Either the occupied edges all share a vertex, or they form a triangle. The occupied faces are totally unconstrained, as a face always shares a vertex with any edge (or other face). The number of speakers of a language is the sum of the number of people on each face and edge incident with that language's vertex.

The sharp case is if all occupied edges share a vertex (see figure below; the occupied edges are shown in red). Then the only way for that vertex to not have at least 3/5 of the conference is for some fraction $x>2/5$ to be on the opposite face $F$ (shown in blue). There's a fraction $1-x$ not on $F$, and at least a third of these must be incident with some vertex of $F$ (by pidgeonhole). This vertex thus has at least $x+(1-x)/3 = 1/3+2x/3$ of the conference, which is $>3/5$ because $x>2/5$.

The other case is where there are three occupied edges forming a triangle, which encloses some face $F$ (shown in blue below). For each vertex of the triangle, there is one edge of the triangle and one face of the tetrahedron which are not incident on it. By pidgeonholing, one of the three vertices of the triangle must have less than a third of the conference in the non-incident edge or face. Thus at least $2/3>3/5$ of the conference speaks the language of that vertex. QED

Answer 2

Here's an alternative argument. Suppose that this is not the case, and the number of people is $n$. If everyone spoke at least three languages then by double counting some language would be spoken by at least $3n/4$. So there is someone who speaks exactly two languages, A and B, say. There is some set $X$ of more than $2n/5$ who don't speak $A$, and a set $Y$ of more than $2n/5$ not speaking $B$; since everyone has to have a language in common with the first person, $X$ and $Y$ are disjoint.

From now on we'll only check whether all pairs one from $X$ and one from $Y$ have a common language. Within $X\cup Y$ there must be at some people who don't speak C, and some who don't speak D. We can't have someone who doesn't speak C in one set and someone who doesn't speak D in the other, so all these people are in the same set, say $X$. This means everyone in $Y$ speaks both C and D, and everyone in $X$ speaks either C or D (or both). Now one of C and D is spoken by at least half of $X$ and all of $Y$, which totals more than $3n/5$, contradiction.

Answer 3

What am I missing? If only one language is used then we are done $n > \frac{3}{5}n$. Say, for two languages $l_1, l_2$ we have a set of people who has to speak to each other i.e all of them has to speak to each other from the condition "any two" attendees must be able to speak to each other. So, every one of them must know $l_1$ or "$l_1$ and $l_2$". Note that you cannot have attendees speak "just" $l_2$ since the ones who speak "just" $l_1$ cannot talk them. So, the set of people has to be $l_1$ and "$l_1$ and $l_2$". So anyway we have $n$ people know one language which is $l_1$ $>\frac{3}{5}n$. Now, add in $l_3$. "just" $l_3$ wouldn't suffice since they can't talk to $l_1$ and "$l_1$ and $l_2$". So, either add $l_1$ to $l_3$ which means there is a language $l_1$ which every body speaks. You can't add $l_2$ to $l_3$ since again "$l_2$ and $l_3$" group cannot talk to "just" $l_1$. Again, there are $n$ people who speak $l_1$ and then we are done. The idea is there can be no two groups in the entire set with each group speaking only one language - languages being different. Since they cannot talk to each other. Now add in $l_4$. Same deal. You have to add $l_4$ to every set other than $l_4$ or add $l_1$ to $l_4$. Either way, we get $n$ attendees speaking one language $l_1$ or $l_4$.