If someone speaks only one language, then the rest of the participants must speak that language too; and then that language is spoken by 100% of the participants. Let's suppose that everyone speaks more than one language. Let $X$ be the set of people that speak exactly two languages, and let $Y$ be the set of people that speak more than 2 languages. Let $n$ be the total number of people. Let $A, B, C, C$ be the set of people that speak each language. We have that $A+B+C+D \ge 2X + 3Y (*)$ We now look at the group of people that speak exactly two languages. We see that is someone is in $AB$ then none is in $CD$; analogously with $AC$ versus $BD$ and $AD$ versus $BD$. Then WLOG we can assume that $X = AB+AC+BC$ or $X = AB+AC+AD$. If we are in the first case, then: $D \le Y$ Then $A+B+C \ge 2X+2Y = 2n$ (using *) Then $\max(A,B,C) \ge \frac 23 n > 0.6n$ If we are in the second case, then: $A \ge X = n - Y$ If $A \ge 0.6n$ then we are done If $A < 0.6n$, then $Y \ge 0.4$ $A+B+C+D \ge 2X + 3Y =2n+Y \ge 2.4n$ (using *) Then $\max(A,B,C,D) \ge \frac {2.4}{4}n = 0.6n$

Please someone let me know if the following solution is correct, because it seems way to easy. Say we have N people. Assume the problem statement holds for K people, for all K<N. If one person speaks exactly one language, then everybody speaks that language, in which case we are done. So assume everybody speaks at least two languages. Let X,Y,Z be the number of people who speak exactly 2,3,4 languages respectively. Then X+Y+Z=N. By the induction hypothesis, among the X+Y people who speak at at most 3 languages, 0.6(X+Y) speak the same language. The Z people who speak all 4 languages of course also speak this language. So 0.6(X+Y)+Z=0.6(N-Z)+Z=0.6N+0.4Z people speak the same language, and this is at least 0.6N. Edit: As JBL pointed out, we can only apply the induction hypothesis if Z>0. I know how to continue the solution, but it is essentially the same as the above post so I will not include the rest.

viperstrike, you have completely failed to analyze the case $Z=0$! Two questions: 1) is this result sharp for infinitely many $n$? (That is, are there actually edge-coverings of $K_n$ with four complete graphs, none using more than 3/5 of the vertices?) 2) what happens if we replace "4" with "$k$"?

1) Yes. 2) I have the answers for all $2\leq k \leq 6$.

Ok, let's see: if we have a sharp solution for $K_m$ then we have a sharp solution for $K_{mn}$ for all positive integers $m$ by "blowing up" solution for $K_n$ and replacing the vertices in each of the covering sets with (disjoint) $m$-sets of vertices. So the fact that it's sharp for $K_5$ (say, take the covering triples 123, 145, 234, 235) means that it's sharp for all multiples of 5. What do you have for other $k$?

The answers for $k =2$ and $3$ are $100\%$, respectively $66.(6)\%$, and they are easy to compute. The answer for $k = 6$ is $50\%$, and is a quite classical result; in an equivalent form, it's question 3, day 1, at the 2013 IMC. The answer for $k = 5$, well ... I can't tell, since I want to use that question in some competition