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: We will show the contrapositive.
That is, assume that
\begin{itemize}
  \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.
  \ii Assume every problem is either solved
  mostly by girls (at most two boys)
  or mostly by boys (at most two girls).
\end{itemize}
Then we will prove that then some contestant
solved more than six problems.

Create a $21 \times 21$ grid with boys as columns
and girls as rows, and in each cell
write the name of a problem solved by the pair.
Color the cell \textbf{green} if at most two girls solved that problem,
and color it \textbf{blue} if at most two boys solved that problem.
(G for girl, B for boy.
It's possible both colors are used for some cell.)

WLOG, there are more green cells than blue,
so (by pigeonhole) take a column (boy) with that property.
That means the boy's column has at least $11$ green squares.
By hypothesis, those corresponds to at least $6$ different problems
solved. Now there are two cases:
\begin{itemize}
  \ii If there are any blue-only squares,
  then that square means a seventh distinct problems.
  \ii If the entire column is green,
  then among the $21$ green squares
  there are at least $11$ distinct problems solved
  in that column.
\end{itemize}

\begin{remark*}
The number $21$ cannot be decreased.
Here is an example of $20$ boys and $20$ girls
who solve problems named $A$-$J$
and $0$-$9$, which motivates the solution to begin with.
\begin{center}
\scriptsize \ttfamily
{\color{green}0000000000}{\color{blue}AABBCCDDEE} \\
{\color{green}0000000000}{\color{blue}AABBCCDDEE} \\
{\color{green}1111111111}{\color{blue}AABBCCDDEE} \\
{\color{green}1111111111}{\color{blue}AABBCCDDEE} \\
{\color{green}2222222222}{\color{blue}AABBCCDDEE} \\
{\color{green}2222222222}{\color{blue}AABBCCDDEE} \\
{\color{green}3333333333}{\color{blue}AABBCCDDEE} \\
{\color{green}3333333333}{\color{blue}AABBCCDDEE} \\
{\color{green}4444444444}{\color{blue}AABBCCDDEE} \\
{\color{green}4444444444}{\color{blue}AABBCCDDEE} \\
{\color{blue}FFGGHHIIJJ}{\color{green}5555555555} \\
{\color{blue}FFGGHHIIJJ}{\color{green}5555555555} \\
{\color{blue}FFGGHHIIJJ}{\color{green}6666666666} \\
{\color{blue}FFGGHHIIJJ}{\color{green}6666666666} \\
{\color{blue}FFGGHHIIJJ}{\color{green}7777777777} \\
{\color{blue}FFGGHHIIJJ}{\color{green}7777777777} \\
{\color{blue}FFGGHHIIJJ}{\color{green}8888888888} \\
{\color{blue}FFGGHHIIJJ}{\color{green}8888888888} \\
{\color{blue}FFGGHHIIJJ}{\color{green}9999999999} \\
{\color{blue}FFGGHHIIJJ}{\color{green}9999999999}
\end{center}
\end{remark*}

\begin{remark*}
  This took me embarrassingly long,
  but part of the work of the problem seemed to be
  finding the right ``data structure'' to get a foothold.
  I think the grid is good because we want to fill each intersection,
  then we consider for each cell a problem to put.

  I initially wanted to capture the full data by writing
  in each green cell the row index of the other girl who solved it,
  and similarly for the blue cells.
  (That led naturally to the colors, there were two types of cells.)
  This was actually helpful for finding the equality case above,
  but once I realized the equality case
  I also realized that I could discard the extra information
  and only remember the colors.
\end{remark*}