Problem 6

In a mathematical competition, in which

6

problems were posed to the participants, every two of these problems were solved by more than

\frac25

of the contestants. Moreover, no contestant solved all the

6

problems. Show that there are at least

2

contestants who solved exactly

5

problems each.

Step 3 of 6: Fourteen pair counts equal

k

and one equals

k+1

Previous step Next step

In plain words

The $15$ integer pair counts are each at least $\frac{2n+1}{5}$ , and their total exceeds $15\cdot\frac{2n+1}{5}$ by just $1$ — so $\frac{2n+1}{5}$ must already be an integer $k$ , with fourteen counts equal to $k$ and a single count equal to $k+1$ .

\sum_{i=1}^5 t_i+\sum_{1\le i<j\le 5}t_{ij}=10+6(n-1)=6n+4=15\cdot\frac{2n+1}{5}+1

Detailed analysis

Summing all $15$ pair counts double-counts each contestant's solved pairs: the one $5$ -solver contributes $\binom52=10$ pairs, and each of the $n-1$ $4$ -solvers contributes $\binom42=6$ pairs, so $\sum t_i+\sum t_{ij}=10+6(n-1)=6n+4$ . On the other hand, each of the $15$ counts is an integer $\ge\frac{2n+1}{5}$ , and $15\cdot\frac{2n+1}{5}=6n+3$ , just $1$ below $6n+4$ . If $\frac{2n+1}{5}$ were not an integer, every count would be $\ge\frac{2n+2}{5}$ and the sum would be $\ge 6n+6$ , impossible; so $k=\frac{2n+1}{5}$ is an integer, fourteen of the $15$ counts equal $k$ , and the remaining one equals $k+1$ .