## Counting with majority I

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.

• #### 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.