Suppose that 21 girls and 21 boys enter a math contest, Show that there is a question that was solved by at least three girls and at least three boys.

Question

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

My question is, why is the number $3$ special here, for example, I tried proving this question in the following way. Fix a girl $g$, this girl could've at most solved $6$ questions $q_1,\dots,q_6$. For the sake of contradiction, assume Each question was solved by at most 2 boys or at most two girls. We first consider if there is at most $2$ boys, then for each of the $6$ questions $g$ answered, there could be at most $2$ pairs involving her and $2$ other boys that solved this question, so for all her $6$ questions, there could be at most $12$ pairs that involve her and other boys. If we sum up this number over all $g$, ($21$ in total), we get the number of pairs is at most $21\times 6 \times 2=252$. This is a contradiction since there are $21^2=441$ pairs of boy-girls, the second case for at most $2$ girls also goes the same by symmetry, so in both cases we have a contradiction.

My question: Why is the number $3$ special here? If it would've been replaced by $4$, then our last equation would be $21 \times 6 \times 3=378$ which is still less than $441$, am I missing something here?

Answer 1

We know that there are at least $21^2 = 441$ connections between a boy and a girl. Let $S$ be the set of such connections ($|S| \ge 441$). Now color all the connections with different colours, depending on the problems. We can now write $S=A \cup B \cup C$, where in the subset $A$ are the connections corresponding to problems solved by at most $2$ girls, in $B$ are the connections corresponding to a problem solved by at most $2$ boys and in $C$ are the connections corresponding to a problem solved by at least $3$ boys and at least $3$ girls. Note that each of connection must be in at least one of this sets and also let's note that $A$ and $B$ mustn't be disjoint. Obviously now our goal is to prove that $C \not = \emptyset$.

So now assume that $C = \emptyset$ and pick a random boy and as it has solved at most $6$ problems we have that there at least one of this problem has been solved by at least $3$ girls. So at most $5$ problems have been solved by at most $2$ girls. That means that each boy contributes to a $A$ by at most $5 \cdot 2 = 10$ connections. Therefore we have that $|A| \le 21 \cdot 10 = 210$. Similar reasoning gives us that $|B| \le 21 \cdot 10 = 210$.

So now:

$$|S| = |A \cup B \cup C| = |A \cup B| = |A| + |B| - |A \cap B| \le 210 + 210 = 420$$

But this contradict the fact that $|S| \ge 441$, meaning that our assumption that $C = \emptyset$ is wrong. Therefore there is a connection in $C$ corresponding to a problem solved by at least $3$ boys and at least $3$ girls, guaranteeing the existence of such problem.

Answer 2

An elegant solution can be found in this book. If you can't read all the book, you can refer to this pdf and cut-the-knots

The idea is as follows: Start by making a $21\times 21$ matrix and assign to each problem a different letter. The entry $(i,j)$ consists of letters (problems) that girl $i$, and boy $j$ both solved.

Observation 1: In each row and in each column there will appear at most 6 distinct letters.

Observation 2: There will be at least 11 entries (squares) in each row, that contains a letter that appears at least 3 times in that row. The same holds for every column.

Color the squares that contain a letter that appears at least 3 times in the same row red.

Color the squares that contain a letter that appear at least 3 times in the same column blue.

By a pidgeon hole argument you can show there is a square that is coloured both red and blue, which shows there is a problem that is solved by at least 3 girls, and 3 boys.

Since $21^2 < 21\times 11 + 21\times 11$ there must be a square that is both red and blue.

Edited:

The above 11 can be got from the above pdf link

at most 5 distinct questions such that for any such question there are at most 2 girls who solved it

This means that with the remaining 11 girls, this boy shares a problem that is solved by at least two other girls.

i.e. $11$ is got from $21-2*5$. This implies the basic idea of this answer is same as Stefan4024's.