$110$ teams participate in a volleyball tournament. Every team has played every other team exactly once (there are no ties in volleyball). Turns out that in any set of $55$ teams, there is one which has lost to no more than $4$ of the remaining $54$ teams. Prove that in the entire tournament, there is a team that has lost to no more than $4$ of the remaining $109$ teams.
I couldn't start, but I did take examples. It's Russia 2015 11.3.
Suppose that the result is false, and let $m>55$ be minimal such that there is a set $T=\{t_1,\ldots,t_m\}$ of $m$ teams such that each team in $T$ has lost to at least $5$ teams in $T$. Let $k\in[m]=\{1,\ldots,m\}$, and let
$$L_k=\big\{i\in[m]\setminus\{k\}:t_i\text{ lost to at most }4\text{ teams in }T\setminus\{t_k\}\big\}\,.$$
The minimality of $m$ implies that $L_k\ne\varnothing$, and we let $f(k)=\min L_k$. Since $t_{f(k)}$ lost to at least $5$ teams in $T$ and at most $4$ teams in $T\setminus\{t_k\}$, it must be the case that $t_{f(k)}$ lost to $t_k$ and to exactly $4$ other teams in $T$.
Let $i\in[m]$, and suppose that $i=f(k)$; then $t_i$ lost to $t_k$. Moreover, $t_i$ lost to exactly $4$ other teams in $T$, so $t_i$ lost to just $5$ teams, and there are therefore at most five $k\in[m]$ such that $f(k)=i$. Let $T_0=\{t_{f(k)}:k\in[m]\}$; we’ve just shown that each team in $T_0$ lost exactly $5$ matches to teams in $T$. This means that the map $f$ is at most $5$-to-$1$, so $m=\big|[m]\big|\le 5|T_0|$, and
$$|T_0|\ge\frac{m}5\ge\left\lceil\frac{56}5\right\rceil=12\,.$$
Now consider just the $\binom{|T_0|}2$ matches between teams in $T_0$. Each of those matches resulted in a loss for some team, and there are $|T_0|$ teams, so the mean number of losses per team is
$$\frac1{|T_0|}\binom{|T_0|}2=\frac{|T_0|-1}2\ge\frac{11}2>5\,,$$
meaning that at least one team in $T_0$ lost more than $5$ matches to teams in $T$. This contradiction shows that no such $m$ exists, i.e., that the result is in fact true.
