2001 IMO Problems/Problem 3

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 1

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.

Solution 2

Let a couple pair be a group of a boy and a girl. There are 441 couple pairs. If there are at most 10 problems, by pigeonhole at least 45 couple pairs got some problem. These 45 couples must involve at least 3 different boys, as there are only 21 couples per girl. Similarly they involve at least 3 girls, so that problem satisfies our requirements.

Now, we have proved the case $n<=10$ . We now aim to use induction to prove the case $n>=11$ , with the base case n=10.

Assume by contradiction that our statement holds for n but not for n+1. Then consolidate two problems a_i and a_j as such; those who solved one of a_i, a_j now solve a_i, and thus who solved neither do not solve a_i.

Note that in any of these consolidations there exists a problem solved by all 3 people (inductive hypothesis).

We can consolidate any of a_i and a_k in the n+1 case; this consolidation must contain a problem 3 boys and girls solved. If it is a problem other than the consolidation, we have our solution in the n+1st case, and we get a contradiction and are done.

Otherwise, that problem is the consolidation, and thus here the consolidation of any two problems is solved by at least 3 boys and girls. Label each of the problems with (b,g), an order pair meaning that problem was solved by b boys and g girls. For problem a_k, let this pair be (b_k,j_k). In this contradiction case, b,g<=2 for all pairs.

Now, note the consolidation of any two problems must have both its values at least 3 and the consolidation a_3 of a_1 and a_2 satisfies b_1+b_2>=b_3>=3, g_1+g_2>=g_3>=3.

If there exists a pair (0,0), then every other pair must have b,g>=3 by the result above. Here we have our contradiction. Let us examine some other cases.

If there exists a pair (0,1) or (1,0) for a problem, WLOG (1,0). Call the solver of the problem Ryan. Now, consider the n-problem case where this problem does not exist and we ignore Ryan’s solution. Given Ryan and any girl, Ryan has solved at least one problem that a girl solved still and Ryan has still solved at most six problems. This consolidation doesn’t change that.

Now, this means every pair must be (1,1), (1,2) or (2,1), or (2,2) because we cannot have (0,1), (1,0), or anything with values at least 3 or else we get our contradiction. We want to show even here there is a contradiction.

Consider just the number of boys that solved each problem. Clearly it must be 1 or 2. If at least two boys solve 1 problem, we get a contradiction as those values (1 and 1) do not sum to at least 3. Then, every problem in the n+1 case was solved by exactly 2 boys with one possible exception. The same holds true of the number of girls that solved the problem.

Now note that every boy has solved some other problems with the set of problems he solved being shared with at least every other girl. That is, for each of the 21 girls there exists a problem both the boy and girl solved.

Also at most 2 girls solved each problem so as the boy solved at most 6 problems then this only accounts for at most 12 girls, contradiction. Then, the statement holds for n+1, and our induction is complete.

2001 IMO (Problems) • Resources
Preceded by Problem 2	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 4
All IMO Problems and Solutions

Page

Toolbox

Search

2001 IMO Problems/Problem 3

Contents

Problem

Solution 1

Solution 2

See also