IMO 2001 Problem 3

Twenty-one girls and twenty-one boys took part in a mathematical competition. It turned out that each contestant solved at most six problems, and for each pair of a girl and a boy, there was at least one problem that was solved by both the girl and the boy. Show that there is a problem that was solved by at least three girls and at least three boys.

===========

Proof:

Color each of \(21\times 21\) squares such that no column or row has more than \(6\) colors. We shall prove that there is a color appearing in at least \(3\) rows and \(3\) columns.

For each row, mark the squares whose color appears more than twice in the same row. Each row then has at least \(21-2\times 5=11\) marked squares. By double counting some column has at least \(11\) marked squares. If these \(11\) squares have \(5\) colors or less, then at least one of them appears \(3\) times or more in that column. Otherwise these \(11\) squares have \(6\) colors and there is no other color in the column, i.e. one of these colors appears at least \(4\) times in it.

Q.E.D.