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.

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