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 4 of 6: An exact linear identity among the

t

Previous step Next step

In plain words

In $1+t_1+t_2+t_3+t_{12}+t_{23}+t_{13}-t_{45}$ , every variable linked only to $\{1,2,3\}$ cancels out, and every variable touching $4$ or $5$ appears a multiple of $3$ times.

(1+t_1+t_2+t_3+t_{12}+t_{23}+t_{13})-t_{45}=3(1+a_4+a_5+b_{14}+b_{15}+b_{24}+b_{25}+b_{34}+b_{35}+2b_{45})

Detailed analysis

Substitute the formulas from Step 2 into $(1+t_1+t_2+t_3+t_{12}+t_{23}+t_{13})-t_{45}$ and check each variable's coefficient: the constant is $(1+3)-1=3$ ; for $m\in\{1,2,3\}$ , $a_m$ appears in one of $t_{12},t_{23},t_{13}$ and in $t_{45}$ ( $1-1=0$ ), while for $m\in\{4,5\}$ it appears in all three of $t_{12},t_{23},t_{13}$ and not in $t_{45}$ ( $3-0=3$ ); for $r,s\in\{1,2,3\}$ , $b_{rs}$ appears in one of $t_1,t_2,t_3$ and in $t_{45}$ ( $1-1=0$ ); for $r\in\{1,2,3\},s\in\{4,5\}$ , $b_{rs}$ appears in two of $t_1,t_2,t_3$ and one of $t_{12},t_{23},t_{13}$ ( $2+1-0=3$ ); and $b_{45}$ appears in all six of $t_1,t_2,t_3,t_{12},t_{23},t_{13}$ ( $6-0=6$ ). Every surviving coefficient is divisible by $3$ .