2. There are 10 students taking part in a mathematics competition. After the competition, they discover that each of them solves exactly 3 problems and any 2 of them solve at least I common problem. What is the minimum number of students who solve a common problem which is solved by most students?
2. Answer: 5 .
Without loss of generality, we may assume that every problem is solved by some student. Let $A$ be one of the students. By assumption each of the 9 other students solves at least one common problem as $\mathrm{A}$. By the pigeonhole principle, there are at least 3 students who solve a common problem which is also solved by $A$. Therefore the minimum number of students who solve a common problem which is solved by most students is at least 4. If the minimum number is exactly 4 , then each problem is solved by exactly 4 students. If there are $n$ problems in the competition, then $4 n=30$. But this is a contradiction since 4 does not divide 30 . Hence the minimum number of students who solve a problem which is solved by most students is at least 5 . We shall show that 5 is in fact the minimum in the following example, where we write (123) to mean that a student solves problems 1,2 and 3 :
(123) (134) (145) (156) (162)
$\begin{array}{lllll}\text { (235) } & (245) & (246) & (346) & (356)\end{array}$