21 players participated in a tennis tournament, in which each pair of players played exactly once and each game had a winner (no ties are allowed). The organizers of the tournament found out that each player won at least 9 games, and lost at least 9. In addition, they discovered cases of three players $A,B,C$ in which $A$ won against $B$, $B$ won against $C$ and $C$ won against $A$, and called such triples "problematic". a) What is the maximum possible number of problematic triples? b) What is the minimum possible number of problematic triples?
Problem
Source: 2021 Israel National Olympiad P6
Tags: combinatorics, Tournament graphs
onyqz
31.07.2024 00:42
I hope it is correct.
We take a directed graph with vertices $v_1, v_2, ..., v_{21}$.
Let $d^+(v_i)$ and $d^-(v_i)$ denote the out-degree and in-degree of the vertex $v_i$, $1 \leq i \leq 21$. Obviously $$\sum_{i=1}^{21}(d^+(v_i)) =\sum_{i=1}^{21}(d^-(v_i))= {21\choose2}=210 $$and
$$d^+(v_i)+d^-(v_i)=20$$
Moreover, observe that we cannot have an out-degree greater than 11 or an in-degree greater than $11$.
We now count the number $T$ of problematic triples $(v_i, v_j, v_k)$ by counting how many triples don't satisfy the condition. We therefore count the triples formed by $2$ outgoing edges and $2$ incoming edges of a vertex respectively. Thus
\begin{align*}
T &= {21\choose3} - \frac{1}{2}\sum_{i=1}^{21}\left({d^+(v_i)\choose2} + {d^-(v_i)\choose2}\right)\\
&= {21\choose3} - \frac{1}{4}\sum_{i=1}^{21}\left((d^+(v_i))^2-d^+(v_i)+(d^-(v_i))^2-d^-(v_i)\right)\\
&= {21\choose3} - \frac{1}{4}\sum_{i=1}^{21}\left((d^+(v_i))^2+(d^-(v_i))^2\right)+105\\
&= {21\choose3} - \frac{1}{4}\sum_{i=1}^{21}\left((20-d^-(v_i))^2+(d^-(v_i))^2\right)+105\\
&= {21\choose3} - \frac{1}{4}\sum_{i=1}^{21}\left(400-40d^-(v_i)+2(d^-(v_i))^2\right)+105\\
&= {21\choose3} - \frac{1}{4}\sum_{i=1}^{21}400+\frac{1}{4}\sum_{i=1}^{21}40d^-(v_i)-\frac{1}{4}\sum_{i=1}^{21}2(d^-(v_i))^2 +105\\
&= {21\choose3}-\frac{1}{2}\sum_{i=1}^{21}(d^-(v_i))^2 +105\\
\end{align*}
Claim: We can have at most $10$ vertices with out-degree $11$.
Proof: Assume we could have more than $10$ vertices with out-degree $11$. The sum of their out-degrees would then be $ \geq 121$. There are $\leq 10$ vertices whose sum of out-degrees has to be $ \leq 210-121 = 89$, but that would mean, we would have a vertex with out-degree $\leq 8$ - contradiction!.
If we have $10$ vertices with out-degree $11$, we must also have $10$ vertices with out-degree $9$ and one vertex with out-degree $10$.
Moreover, note that for an integer, we have $2x^2 < 2x^2+2 = (x+1)^2+(x-1)^2$. Therefore
$$ 21\cdot10^2 \leq \sum_{i=1}^{21}(d^-(v_i))^2 \leq 10\cdot11^2+10\cdot9^2+10^2$$and we get:
$$385 \geq T \geq 375$$Equality can be achieved. $\square$