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 6 of 6: Pick a split that avoids the single

(k+1)

term

Previous step Next step

In plain words

Only seven of the fifteen $t$ 's appear in the congruence for a given split $\{a,b,c\}\cup\{d,e\}$ , so we can always choose the split so that all seven equal $k$ — turning the congruence into $k\equiv 1+6k\pmod3$ , i.e. $0\equiv1\pmod3$ .

k\equiv 1+6k\pmod 3\ \Longrightarrow\ 1\equiv 0\pmod 3\quad(\text{contradiction})

Detailed analysis

By Step 3, fourteen of the fifteen $t$ 's equal $k$ and only one equals $k+1$ . If the exceptional $(k+1)$ term is some $t_e$ , pick $\{a,b,c\}\subset\{1,2,3,4,5\}\setminus\{e\}$ and let $d$ be the remaining index; if instead the exceptional term is some $t_{xy}$ , pick $\{a,b,c\}$ so that $\{x,y\}$ is neither $\{d,e\}$ nor a subset of $\{a,b,c\}$ (i.e. put $x\in\{a,b,c\}$ and $y\in\{d,e\}$ ). Either way, the exceptional term does not appear among $t_{de},t_a,t_b,t_c,t_{ab},t_{bc},t_{ca}$ , so all seven of those equal $k$ . Step 5 then gives $k\equiv 1+6k\pmod3$ , i.e. $0\equiv1\pmod3$ , a contradiction. Therefore at least $2$ contestants solved $5$ problems.