Difference between revisions of "2001 IMO Problems/Problem 3"
(→Solution: template) |
I like pie (talk | contribs) m |
||
| Line 1: | Line 1: | ||
| − | ==Problem== | + | == 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. | 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== | + | == 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. | 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. | ||
| Line 15: | Line 15: | ||
{{incomplete|solution}} | {{incomplete|solution}} | ||
| − | + | == See also == | |
| − | |||
{{IMO box|year=2001|num-b=2|num-a=4}} | {{IMO box|year=2001|num-b=2|num-a=4}} | ||
[[Category:Olympiad Combinatorics Problems]] | [[Category:Olympiad Combinatorics Problems]] | ||
Revision as of 20:56, 21 April 2008
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.
See also
| 2001 IMO (Problems) • Resources | ||
| Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
| All IMO Problems and Solutions | ||
