2001 IMO Problems/Problem 3

From AoPSWiki

Problem

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.

Solution

Since there is a common problem that was solved by a pair of a girl and a boy, each person solved at least one problem. Now we prove that three boys will solve a problem that one of the girls gets.

Let's say that a girl solved only one problem. Then all 21 boys will have solved that problem.

Now we assume that a girl got two problems. Therefore, each boy must solve at least one of those problems. From the pigeonhole principle, at least boys must have solved one of those problems.

We give a similar argument for three, four, five, and six problems.

Therefore, at least three boys will solve a problem that one of the girls gets.

This solution is incomplete. You can help us out by completing it.

See also

2001 IMO (Problems)
Preceded by Problem 2	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 4