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"

m
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.
+
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.
  
−
Let's say that a girl solved only one problem. Then all 21 boys will have solved that problem.
+
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.
  
−
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.
+
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.
  
−
We give a similar argument for three, four, five, and six problems.
+
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.  
  
−
Therefore, at least three boys will solve a problem that one of the girls gets.
+
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.
−
 
 
−
{{incomplete|solution}}
 
  
 
== See also ==
 
== See also ==

Revision as of 00:05, 25 December 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 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.

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.

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

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 $21\times 11$ 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 $12\times 5$, 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

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=28747"