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.
