MathDB
At least ceil[2n/9] of the languages can be chosen

Source: Middle European Mathematical Olympiad 2011 - Team Compt. T-4

September 6, 2011
ceiling functionfloor functiongraph theoryexpected valuecombinatorics proposedcombinatoricsProbabilistic Method

Problem Statement

Let n≥3n \geq 3 be an integer. At a MEMO-like competition, there are 3n3n participants, there are n languages spoken, and each participant speaks exactly three different languages. Prove that at least ⌈2n9⌉\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. ⌈x⌉\lceil x\rceil is the smallest integer which is greater than or equal to xx.
Back to ProblemsView on AoPS