Counting with majority II

Task number: 3921

Twenty students wrote a test that consists of four assignments. For each pair of students, we would find an assignment in the test that they both solved correctly. Prove that more than half of the students solved some of the assignments correctly.

  • Solution

    Suppose for the contrary that each assignment is solved by at most 10 students.

    We estimate the total number of assignments solved by pairs of students in two ways, or the number of triplets \( (s, t, u) \), meaning that students \( s \) and \( t \) solved the assignment \( u \).

    \(\#(s,t,u)\ge\binom{20}{2}=190\), because for each pair of students \( s \) and \( t \) at least one assignment can be found to complete the triple.

    \(\#(s,t,u)\le 4\cdot\binom{10}{2}=180\), because each of the four assignment could be solved together by at most \(\binom{10}{2}\) pairs of students.

    Comparing the two estimates, we get \( 190 \le 180 \). It follows from this contradiction that the assumption does not apply and therefore there is an assignment solved by the majority of students.

Difficulty level: Moderate task
Reasoning task
Proving or derivation task
Solution require uncommon idea
Cs translation
Send comment on task by email