has somebody a solution? ideas,hints...something....

hint: use the probabilistic method.

can you elaborate it?

Another way to communicate the problem is: We have bipartite graph $G$ with vertices in $A \cup B, \, |A|=3n,\, |B|=n.$ Each vertice of $A$ is connected with $3$ vertices of $B$. Prove that we can delete some vertices from $B$, and to left at least $\left\lceil\frac{2n}{9}\right\rceil$, so that in the induced graph every vertice of $A$ has degree at most 2. Prove (a sketch of). $G$ has $9n$ edges, $|B|=n$, so there is a vertice $X$ in $B$ with degree at least $9$. If we delete $X$, at least $9$ vertices of $A$ will be OK(will have degree at most $2$). Let also omit all vertices of $G$, that are connected with $X$(at least $9$), so we obtain graph $G_1$, with vertices $|A_1| \le 3n-9,\, |B_1|=n-1$. With $G_1$ we can proceed with the same way, there will exist $X_1 \in B_1$ with degree at least $\frac{3(3n-9)}{n-1}$ ...etc., so if at $k$-th step $|A_k|=a_k, \, |B_k|=b_k$, at $k+1$-th $a_{k+1} \le a_k - \frac{3a_k}{b_k}, \, b_{k+1}=b_k -1$. The question is at which $k$, $a_k$ will be $0$. It can be seen that when $k \le \frac{n}{4}$, it is possible at every step to decrease $|A| $ with $6$ , so after $k=\left\lfloor{\frac{2n}{9}} \right\rfloor < \frac{n}{4}$ steps $A$ will remain with no more than $\frac{5n}{3}$ vertices and $|B|=\left\lceil\frac{7n}{9}\right\rceil$. Now, at every next step $|A|$ will decrease at least with $3$, so after another $\left\lfloor\frac{5n}{9}\right\rfloor$ steps, $A$ will be empty. At this moment $B$ will consist with at least $\left\lceil\frac{2n}{9}\right\lceil$ vertices, which comply the requirements.

Why in topics about problems for MEMO there are more bluffs than correct solutions ? Think about it once again. Solution: Take random subset S of languages, where $|S|=m=\lfloor \frac{n}{3}\rfloor$ (every subset with equal probability). Expected value participants with degree 3 will be equal $\frac{{m \choose{3}}}{{n \choose{3}}} \cdot 3n<3n(\frac{m}{n})^3 \leq \frac{n}{9}$, so there exist subset P, where $|P|=\lfloor \frac{n}{3}\rfloor$ and there are at most $\lfloor\frac{n}{9}\rfloor$ guys with degree 3. Now we delete from P one language for every guy and we get subset of at least $\lfloor \frac{n}{3}\rfloor -\lfloor\frac{n}{9}\rfloor$ languages. We're not done only when $ n\equiv_9 1, 2, 5$, but while proving this cases it's sufficient to more precisely estimate expected value.

I thought about dgrozev's solution once again and I realized that I'm not sure if reason, why I thought it's wrong, is correct, so for now I'm not saying that solution is wrong for 100%, but for me it looks shifty.

Easier: Choose every language with probability $1/3$, the choices are mutually independent. This generates a set $M$. Consider an arbitrary contestant: The probability that all the languages spoken by this contestant are in $M$ is $1/27$. If this is the case, remove arbitrarily one of those three languages from the set $M$. This generates a set $N$ with $E(|N|) \ge n/3-3n/27=2n/9$. Hence there is at least one set $N$, such that $|N|\ge \lceil2n/9\rceil$.

Swistak wrote: I thought about dgrozev's solution once again and I realized that I'm not sure if reason, why I thought it's wrong, is correct, so for now I'm not saying that solution is wrong for 100%, but for me it looks shifty. I could clear up what You didn't get, If You were more precise! ( instead of writing judgements.)

You said that in the end in every step $|A|$ will decrease at least with 3, but what about case when first contestant speak in first, second and third language and no one else will speak in these languages? This case shows that if you want to delete this guy, that have to be one step, when $|A|$ will decrease with only 1. I don't know where are these $6$ and $3$ from.