Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2001 IMO Problems/Problem 3"
(→‎Solution)
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 solves.
 
  
−
Since every girl solves at least one problem in common with another guy, we can conclude using a version of the pigeon hole principle that there is a set of at least eleven guys such that the problem solved in common by one such guy from the set and the girl has also been solved by at least two other guys.
+
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).
  
−
Now each guy solves a problem in common with every girl, which means by the pigeon hole principle that given a guy, there is a problem solved by him such that at least three girls have solved that problem.
+
The boys have solved a total of at most <math>21\times 6</math> 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 <math>21\times 6</math>.
  
−
Let M be the multiset of problems solved by the guys, so that every problem is repeated in the set as many times as the number of guys solving it. The cardinality of this set is at most <math>21\times 6</math>. Let N be the subset of M of problems which were solved by at least three girls. Clearly, the cardinality of N is at least 21, since each guy solves a problem that at least three girls solve.  
+
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 <math>21\times 11</math> 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 <math>21\times 5</math> problems in A have been marked since <math>21\times 5 \times 2<21\times 11</math> (there are a total of <math>21\times 11</math> 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.
−
 
 
−
Then for every girl, mark off each problem in M that has been solved by her and at least three guys in the multiset, which would result in at least <math>21\times 11</math> markings, i.e. at least 11 for every girl because of the observation above. If a problem is marked more than twice then three girls have solved a problem that at least three guys have solved. If each problem is marked only at most twice then the number of marked problems is strictly more than <math>12\times 5</math>, which means that one of the problems in N have been marked. Then it is clear that this problem has been solved by at least three girls and at least three guys. So there has to be such a problem that is solved by at least three people of each gender.
 
  
 
== See also ==
 
== See also ==

Revision as of 06:04, 18 June 2010

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

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 $21\times 6$ 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 $21\times 6$.

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 $21\times 11$ 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 $21\times 5$ problems in A have been marked since $21\times 5 \times 2<21\times 11$ (there are a total of $21\times 11$ 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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_IMO_Problems/Problem_3&oldid=34998"