Difference between revisions of "2001 IMO Problems/Problem 3"
(creation) |
(partial solution... help here.) |
||
| Line 3: | Line 3: | ||
==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. | ||
| + | |||
| + | 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 <math>\lfloor \frac{21}{2} \rfloor</math> 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. | ||
| + | |||
{{solution}} | {{solution}} | ||
| + | |||
| + | |||
{{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 21:28, 27 October 2007
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 problem needs a solution. If you have a solution for it, please help us out by adding it.
| 2001 IMO (Problems) • Resources | ||
| Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
| All IMO Problems and Solutions | ||
