# Counting pigeonhole principle

Suppose that $21$ girls and $21$ boys enter a mathematics competition. Furthermore, suppose that each entrant solves at most six questions, and for every boy-girl pair, there is at least one question that they both solved. Show that there is a question that was solved by at least three girls and at least three boys.

My approach:

Total number of entrant$=21+21=42$ and each entrant solves at most $6$ question and every girl boy pair solves $1$ question ...so in worst case total number of pigeons$=42*6-21\text{(pairs)}=231$...now we have $42$ number of pigeon holes(entrants) ,so using pigeon hole we have $\lfloor(231/42)\rfloor=6$ ....not getting how to do further ... I know I am wrong please help me out ..!

• This is from IMO 2001 - see here. – pi66 Aug 25 '16 at 7:14
• There at most 42 x 6 = 252 correct answers. There are 21! Boy-girl pairs. They each answer a question right but there are only 252 question so at least one question was answered correctly by 21!/42x6 different pairs. The most different pairs you can pick and only pick two boys is 21x20. Ditto girls. So if you pick more than 2x21x20 different pairs at least one will have at least 3 different girls and three different boys. 21!/42x6 > 2x21x20 so at least one question was answered by at least three different boys and three different girls. – fleablood Aug 25 '16 at 8:05

A full solution can be found in the link I gave in the comments, but since this is a rather tricky problem, let me give step-by-step hints in case you want to work out the details yourself.

1) Let $n$ be the number of questions. Set up a table with $n$ rows and $441=21^2$ columns, where each row corresponds to a question and each column to a (boy, girl) pair. Let an entry be $1$ if both members of the pair solve the question, otherwise $0$.

2) You know that for every (boy, girl) pair, there is at least one question that they both solve. What does this tell you about the number of $1$'s in the table?

3) You want to show that some row (question) is solved by at least three boys and three girls. So assume for contradiction that each row is solved by at most two boys or two girls.

4) Fix a girl $g$. All columns that correspond to her can have a $1$ in at most six rows. There are at least $21$ $1$'s in these columns and the six rows. If a row (question) is solved by at most two boys, there are at most two $1$'s in the row. Out of the (at most) six rows, at most how many rows solved by at most two boys can there be? At most how many $1$'s are there in total among these rows?

5) Summing up over all girls $g$, at most how many $1$'s are there in rows solved by at most two boys? By symmetry, there are at most the same number of $1$'s in rows solved by at most two girls. But these two classes together include all rows, by our assumption for contradiction.

6) Derive a contradiction between 2) and 5).

• In each row ...we can have maximum 6 "1" in the cells so total 21*6=126 "1" ....but not getting how to count column ...i am not getting please help me out @pi66 – virat Aug 25 '16 at 12:07
• Careful with how this table is defined ... a row corresponds to a question, not a boy/girl. – pi66 Aug 25 '16 at 12:18
• am i not right @pi66 ?don't we have 6 "1" in each row...resulting to 21*6 "1"???? – virat Aug 25 '16 at 13:09