Problem: In a mathematical competition $6$ problems were posed to the contestants.
Each pair of problems was solved by more than $\frac{2}{5}$ of the contestants.
Nobody solved all 6 problems.
Show that there were at least $2$ contestants
who each solved exactly $5$ problems.

\end{enumerate}

Solution: Assume not and at most one contestant solved five problems.
By adding in solves,
we can assume WLOG that one contestant solved problems one through five,
and every other contestant solved four of the six problems.

We split the remaining contestants based on whether they solved P6.
Let $a_i$ denote the number of contestants who solved
$\{1,2,\dots,5\} \setminus \{i\}$ (and missed P6).
Let $b_{ij}$ denote the number of contestants who solved
$\{1,2,\dots,5,6\} \setminus \{i,j\}$, for $1 \le i < j \le 5$
(thus in particular they solved P6).
Thus
\[ n = 1 + \sum_{1 \le i \le 5} a_i + \sum_{1 \le i < j \le 5} b_{ij} \]
denotes the total number of contestants.

Considering contestants who solved P1/P6 we have
\[ t_1 \coloneq b_{23} + b_{24} + b_{25} + b_{34} + b_{35} + b_{45} \ge \frac25n + \frac15 \]
and we similarly define $t_2$, $t_3$, $t_4$, $t_5$.
(We have written $\frac25n+\frac15$ since we know
the left-hand side is an integer strictly larger than $\frac25n$.)
Also, by considering contestants who solved P1/P2 we have
\[ t_{12} = 1 + a_{3} + a_{4} + a_{5} + b_{34} + b_{35} + b_{45}
  \ge \frac25n + \frac15 \]
and we similarly define $t_{ij}$ for $1 \le i < j \le 5$.

\begin{claim*}
  The number $\frac{2n+1}{5}$ is equal to some integer $k$,
  fourteen of the $t$'s are equal to $k$,
  and the last one is equal to $k+1$.
\end{claim*}
\begin{proof}
First, summing all fifteen equations gives
  \begin{align*}
    6n+4 = 10 + 6(n-1) &= 10
      + \sum_{1 \le i \le 5} 6a_i + \sum_{1 \le i < j \le 5} 6b_{ij} \\
      &= \sum_{1 \le i \le 5} t_i + \sum_{1 \le i < j \le 5} t_{ij}.
  \end{align*}
  Thus the sum of the $15$ $t$'s is $6n+4$.
  But since all the $t$'s are integers at least
  $\frac{2n+1}{5} = \frac{6n+3}{15}$, the conclusion follows.
\end{proof}

However, we will also manipulate the equations to get the following.
\begin{claim*}
  We have
  \[ t_{45} \equiv 1 + t_1 + t_2 + t_3 + t_{12} + t_{23} + t_{31} \pmod 3. \]
\end{claim*}
\begin{proof}
  This follows directly by computing the coefficient of the $a$'s and $b$'s.
  We will nonetheless write out a derivation of this equation, to
  motivate it, but the proof stands without it.

  Let $B = \sum_{1 \le i < j \le 5} b_{ij}$ be the sum of all $b$'s.
  First, note that
  \begin{align*}
    t_1 + t_2 &= B + b_{34} + b_{45} + b_{35} - b_{12} \\
    &= B + \left( t_{12}-1-a_3-a_4-a_5 \right) - b_{12} \\
    \implies b_{12} &= B - (t_1 + t_2) + t_{12} - 1 - (a_3+a_4+a_5).
  \end{align*}
  This means we have more or less solved for each $b_{ij}$
  in terms of only $t$ and $a$ variables.
  Now
  \begin{align*}
    t_{45} &= 1 + a_1 + a_2 + a_3 + b_{12} + b_{23} + b_{31} \\
    &= 1 + a_1 + a_2 + a_3 \\
      &+ [B - (t_1 + t_2) + t_{12} - 1 - (a_3+a_4+a_5)] \\
      &+ [B - (t_2 + t_3) + t_{23} - 1 - (a_1+a_4+a_5)] \\
      &+ [B - (t_3 + t_1) + t_{13} - 1 - (a_2+a_4+a_5)] \\
    &\equiv 1 + t_1 + t_2 + t_3 + t_{12} + t_{23} + t_{31} \pmod 3
  \end{align*}
  as desired.
\end{proof}

However, we now show the two claims are incompatible
(and this is easy, many ways to do this).
There are two cases.
\begin{itemize}
  \ii Say $t_5 = k+1$ and the others are $k$.
  Then the equation for $t_{45}$ gives that $k \equiv 6k+1 \pmod 3$.
  But now the equation for $t_{12}$ give $k \equiv 6k \pmod 3$.
  \ii Say $t_{45} = k+1$ and the others are $k$.
  Then the equation for $t_{45}$ gives that $k+1 \equiv 6k \pmod 3$.
  But now the equation for $t_{12}$ give $k \equiv 6k+1 \pmod 3$.
\end{itemize}


\begin{remark*}
  It is significantly easier to prove that there
  is at least one contestant who solved five problems.
  One can see it by dropping the $+10$ in the proof of the claim,
  and arrives at a contradiction.
  In this situation it is not even necessary to set up
  the many $a$ and $b$ variables;
  just note that the expected number of contestants
  solving any particular pair of problems is
  $\frac{\binom42n}{\binom62} = \frac25n$.

  The fact that $\frac{2n+1}{5}$
  should be an integer also follows quickly,
  since if not one can improve the bound to $\frac{2n+2}{5}$
  and quickly run into a contradiction.
  Again one can get here without setting up $a$ and $b$.

  The main difficulty seems to be the precision required
  in order to nail down the second $5$-problem solve.
\end{remark*}

\begin{remark*}
  The second claim may look miraculous,
  but the proof shows that it is not too unnatural
  to consider $t_1 + t_2 - t_{12}$ to isolate $b_{12}$
  in terms of $a$'s and $t$'s.
  The main trick is: why mod $3$?

  The reason is that if one looks closely, for a
  fixed $k$ we have a system of $15$ equations in $15$ variables.
  Unless the determinant $D$ of that system happens to be zero,
  this means there will be a rational solution in $a$ and $b$,
  whose denominators are bounded by $D$.
  However if $p \mid D$ then we may conceivably run into mod $p$
  issues.

  This motivates the choice $p = 3$,
  since it is easy to see the determinant is divisible by $3$,
  since constant shifts of $\vec a$ and $\vec b$ are also solutions mod $3$.
  (The choice $p = 2$ is a possible guess as well for this reason,
  but the problem seems to have better $3$-symmetry.)
\end{remark*}