IMO 2001 SL C8

Origin: GER | Category: Combinatorics

Problem

Twenty-one girls and twenty-one boys took part in a mathematical competition. It turned out that (i) each contestant solved at most six problems, and (ii) 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

We say that a problem is difficult for boys if at most two boys solved it, and difficult for girls if at most two girls solved it. Let us estimate the number of pairs boy-girl both of whom solved some problem difficult for boys. Consider any girl. By the condition (ii), among the six problems she solved, at least one was solved by at least 3 boys, and hence at most 5 were difficult for boys. Since each of these problems was solved by at most 2 boys and there are 21 girls, the considered number of pairs does not exceed 5 \cdot 2 \cdot 21 = 210. Similarly, there are at most 210 pairs boy-girl both of whom solved some problem difficult for girls. On the other hand, there are 212 > 2 \cdot210 pairs boy-girl, and each of them solved one problem in common. Thus some problems were difficult neither for girls nor for boys, as claimed. Remark. The statement can be generalized: if 2(m −1)(n −1) + 1 boys and as many girls participated, and nobody solved more than m problems, then some problem was solved by at least n boys and n girls.