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: template)
 
(7 intermediate revisions by 3 users not shown)
Line 1: Line 1:
−
==Problem==
+
== 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.
 
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 ==
−
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.
+
https://www.youtube.com/watch?v=zfsyYMbUwno
  
−
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.
+
== Solution ==
  
−
We give a similar argument for three, four, five, and six problems.
+
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).
−
 
 
−
Therefore, at least three boys will solve a problem that one of the girls gets.
 
−
 
 
−
{{incomplete|solution}}
 
  
 +
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>.
  
 +
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.
  
 +
== See also ==
 
{{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]]

Latest revision as of 06:27, 26 November 2020

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 $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=138526"