Counting with majority I
Task number: 3920
In the credit test, each student solved at least a third of all assignments. In addition, at least half of the students solved at least two-thirds of the assignments. Show that the test contains an assignment that has been solved by at least half of the students.
Hint
Prove your existence by contradiction.
Solution
Suppose for a contradiction that less than half of the students have solved each assignment.
Let’ denote by \( n \) the number of students and by \( m \) the number of assignments.
In two ways, we estimate the total number of problems solved by all students, i.e. the number of pairs \( (s, u) \), meaning that the student \( s \) solved the assignment \( u \).
\(\#(s,u)< m\cdot\frac{n}{2} \), because each of the \( m \) assignments has been solved by less than \(\frac{n}{2} \) students.
\(\#(s,u)\ge n\cdot\frac{m}{3} + \frac{n}{2}\cdot \frac{m}{3}\), because each of \( n \) students solved at least \(\frac{m}{3} \) assignments and in addition \(\frac{n}{2} \) students solved one more third of the assignments.
Comparing the two estimates, we get \(\frac{mn}{2}< \frac{mn}{2}\). It follows from this contradiction that the assumption does not apply and therefore there is a problem solved by the majority of students.
