IMO 2001 Q3 #
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 #
Note that not all of the problems a girl $g$ solves can be "hard" for boys, in the sense that at most two boys solved it. If that was true, by condition 1 at most $6 × 2 = 12$ boys solved some problem $g$, but by condition 2 that property holds for all 21 boys, which is a contradiction.
Hence there are at most 5 problems $g$ solved that are hard for boys, and the number of girl-boy pairs who solved some problem in common that was hard for boys is at most $5 × 2 × 21 = 210$. By the same reasoning this bound holds when "girls" and "boys" are swapped throughout, but there are $21^2$ girl-boy pairs in all and $21^2 > 210 + 210$, so some girl-boy pairs solved only problems in common that were not hard for girls or boys. By condition 2 the result follows.
The conditions on the problems the girls and boys solved, represented as functions from Fin 21
(index in cohort) to the finset of problems they solved (numbered arbitrarily).
Every girl solved at most six problems.
Every boy solved at most six problems.
Every girl-boy pair solved at least one problem in common.