MEMO 2011 ekipno problem 4

  Avg: 3,0
  Avg: 7,0
Dodao/la: arhiva
28. travnja 2012.
Let n \geq 3 be an integer. At a MEMO-like competition, there are 3n participants, there are n languages spoken, and each participant speaks exactly three different languages. Prove that at least \left\lceil\frac{2n}{9}\right\rceil of the spoken languages can be chosen in such a way that no participant speaks more than two of the chosen languages.

Note. \lceil x\rceil is the smallest integer which is greater than or equal to x.
Izvor: Srednjoeuropska matematička olimpijada 2011, ekipno natjecanje, problem 4