Difference between revisions of "2001 IMO Problems/Problem 3"
(partial solution... help here.) |
(→Solution: template) |
||
| Line 7: | Line 7: | ||
Let's say that a girl solved only one problem. Then all 21 boys will have solved that problem. | 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. | + | 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>\left\lfloor \frac{21}{2} \right\rfloor</math> boys must have solved one of those problems. |
We give a similar argument for three, four, five, and six problems. | We give a similar argument for three, four, five, and six problems. | ||
| Line 13: | Line 13: | ||
Therefore, at least three boys will solve a problem that one of the girls gets. | Therefore, at least three boys will solve a problem that one of the girls gets. | ||
| − | {{solution}} | + | {{incomplete|solution}} |
Revision as of 14:53, 28 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.
| 2001 IMO (Problems) • Resources | ||
| Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
| All IMO Problems and Solutions | ||
