Difference between revisions of "2001 IMO Problems/Problem 3"
| (One intermediate revision by one other user not shown) | |||
| Line 2: | Line 2: | ||
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 | + | == Video solution == |
| + | |||
| + | https://www.youtube.com/watch?v=zfsyYMbUwno | ||
| + | |||
| + | == Solution == | ||
For each girl, we know that there is a boy who solved a problem in common with her. Since a girl solves at most six problems, for a girl and her set of six problems there are at least 11 boys who solved a problem in common with the girl such that at least three boys solved that common problem. (This is a simple application of the pigeon hole principle where the problems solved by the girl are the holes and the boys are the pigeons, and the guy/pigeon enters a hole/problem which he solved in common with the girl). | For each girl, we know that there is a boy who solved a problem in common with her. Since a girl solves at most six problems, for a girl and her set of six problems there are at least 11 boys who solved a problem in common with the girl such that at least three boys solved that common problem. (This is a simple application of the pigeon hole principle where the problems solved by the girl are the holes and the boys are the pigeons, and the guy/pigeon enters a hole/problem which he solved in common with the girl). | ||
Latest revision as of 06:27, 26 November 2020
Contents
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.
Video solution
https://www.youtube.com/watch?v=zfsyYMbUwno
Solution
For each girl, we know that there is a boy who solved a problem in common with her. Since a girl solves at most six problems, for a girl and her set of six problems there are at least 11 boys who solved a problem in common with the girl such that at least three boys solved that common problem. (This is a simple application of the pigeon hole principle where the problems solved by the girl are the holes and the boys are the pigeons, and the guy/pigeon enters a hole/problem which he solved in common with the girl).
The boys have solved a total of at most 
problems.We view this as a set with repeated elements i.e. if a problem is solved by more than one boy it appears as many times as the number of boys who have solved it. Let this set of problems be A. Clearly, A has size .
We mark each problem in A which has been solved by at least three boys and a girl. And we mark it the number of times that is the same as the number of girls that has solved it. Since there are a total of 
marks (since there are at least 11 marks for each girl, by the discussion above), either a problem is marked at least thrice, in which case we're done since then it has been solved by at least three boys and three girls. Or each problem has been marked at most twice. In this case it is clear that more than 
problems in A have been marked since 
(there are a total of marks. This means that there is a boy such that all six of his problems have been marked. But then by our discussion in the first paragraph we know there must a problem that this boy has solved which has been solved by at least three girls. Therefore it must be true that there is a problem such that it has been solved by at least three people of each gender.
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 | ||
