Proof by double counting

Question

Two hundred students participated in a math contest. The had six problems to solve. Each problem was correctly solved by at least 120 participants. Prove, using double counting, that there must be two participants such that every problem was solved by at least one of these students.

My approach was that I have proved that maximum number of questions solved by a student is at least 4 and was able to prove the given statement, but is it double counting or not? If it isn't how to prove using double counting?

Answer 1

I would call this the pigeonhole principle rather than double counting, but I suspect they mean the same thing.

You say you can show at least one student answered at least $4$ questions correctly. Presumably this is based on something like $\frac{120\times 6}{200}=3.6>3$. You could expand this to saying at least $120$ students answered at least $4$ questions correctly since $\frac{120 \times 4 +80\times 3}{200}=3.6$, but do not need to.

• Choose such a student and $4$ of the questions they answered correctly.
• That leaves $2$ questions, each answered correctly by at least $120$ students
• So at least $120\times 2-200=40$ students answered both of these $2$ correctly, using the pigeonhole principle
• Choose one such student.
• Between them, the two chosen students answered all $6$ questions correctly.