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 1 of 6: Normalize to one

5

-solver and

(n-1)

4

-solvers

Previous step Next step

In plain words

If a counterexample exists with at most one $5$ -solver, handing extra solved problems to everyone else until the one top contestant has $5$ and all others have $4$ only increases every pair count, so the counterexample stays valid and becomes completely rigid.

n=1+\sum_{i=1}^5 a_i+\sum_{1\le i<j\le 5}b_{ij}

Detailed analysis

Assume for contradiction that at most one contestant solved $5$ problems. Adding solved problems to contestants only increases each pair count without violating any hypothesis, so we may assume without loss of generality that one contestant solved problems $1,2,3,4,5$ (missing problem $6$ ) and every other contestant solved $4$ problems. Among the remaining $n-1$ contestants, let $a_i$ ( $1\le i\le5$ ) be the number who missed problem $6$ and problem $i$ , and let $b_{ij}$ ( $1\le i<j\le5$ ) be the number who solved problem $6$ and missed problems $i,j$ ; then $n=1+\sum_{i=1}^5 a_i+\sum_{1\le i<j\le5}b_{ij}$ .