Problem
COM-B2-M01-P016 Common Solved Problems
There are \(21\) students and \(10\) problems. Each student solved at least \(6\) problems. Prove that two students solved at least \(4\) common problems.
Count pairs of students who solved the same problem.
Let \(d_j\) be the number of students who solved problem \(j\). Then \(\sum d_j\ge21\cdot6=126\). The number of triples \((\{u,v\}, problem)\), where both students solved the problem, is \(\sum_{j=1}^{10}\binom{d_j}{2}\). With total \(126\) over \(10\) problems, this sum is minimised by the balanced distribution \(13,13,13,13,13,13,12,12,12,12\), giving \(6\binom{13}{2}+4\binom{12}{2}=732\). There are \(\binom{21}{2}=210\) pairs of students. If every pair had at most \(3\) common solved problems, there would be at most \(630\) triples, a contradiction. Hence some pair has at least \(4\) common solved problems.
A difficult double-counting plus convexity problem.