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 2 of 6: Write out all

15

pair-solve counts

Previous step Next step

t_i=\sum_{\substack{1\le r<s\le 5\\ r,s\ne i}}b_{rs}\ge\frac{2n+1}{5},\quad t_{ij}=1+\sum_{m\ne i,j}a_m+\sum_{\{r,s\}\cap\{i,j\}=\emptyset}b_{rs}\ge\frac{2n+1}{5}

Detailed analysis

For $1\le i\le5$ , let $t_i$ be the number of contestants who solved both problem $i$ and problem $6$ ; only the $b_{rs}$ with $i\notin\{r,s\}$ contribute, giving $t_i=\sum_{r,s\ne i}b_{rs}$ ( $6$ terms). For $1\le i<j\le5$ , let $t_{ij}$ be the number who solved both problem $i$ and problem $j$ ; the single $5$ -solver contributes $1$ , the $a_m$ with $m\notin\{i,j\}$ contribute ( $3$ terms), and the $b_{rs}$ disjoint from $\{i,j\}$ contribute ( $3$ terms). Each of the $15$ counts $t_i,t_{ij}$ is an integer strictly greater than $\frac25 n$ , hence at least $\frac{2n+1}{5}$ .