In a math competition with $8$ students and $8$ problems, if each problem is solved by $5$ students, then two students together solve all problems.

Question

Eight students are entered in a math competition. They all have to solve the same set of $8$ problems. After correction, we see that each problem was correctly resolved by exactly $5$ students. Show that there are two students who together have solved all the problems.

Answer 1

For each pair of students, consider the set of those problems which was not solved by them. There exist $${8 \choose 2} = 28 $$sets; we have to prove that at least one set is empty.

For each problem, there are at most $8-5=3$ students who did not solve it. From these students at most

$${3\choose 2}= 3$$ pairs can be selected, so the problem can belong to at most 3 sets. The 8 problems together can belong to at most $8\cdot3 =24$ sets. Hence, at least $28 − 24 = 4$ sets must be empty. Hence proved, so that's it.