2001 IMO Problems/Problem 3

Revision as of 15:53, 28 October 2007 by Temperal (talk | contribs) (Solution: template)

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 $\left\lfloor \frac{21}{2} \right\rfloor$ 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.

Template:Incomplete


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