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

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?

Solution 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

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