2022 CGMO

Proof. We prove by contradiction: assume the conclusion is false. Suppose that the teams $P_1,\cdots ,P_k$ all have won less than $\frac{n}{4}$ games, while the remaining $3n-k$ teams, $Q_1,\cdots ,Q_{3n-k}$ all have won at least $\frac{n}{4}$ games. Based on the assumption of proof by contradiction, the number of defeats for $Q_1,\cdots ,Q_{3n-k}$ is also less than $\frac{n}{4}$. Since the total number of victories for all teams is $3n^2$, there must be at least one team with no fewer than $n$ victories, implying that $3n-k>0$. The number of matches between teams $P_1,\cdots ,P_k$ cannot exceed the sum of their victories, so it is not more than $\frac{nk}{4}$. In a similar fashion, the number of matches between teams $Q_1,\cdots ,Q_{3n-k}$ cannot exceed the sum of their defeats, so it is less than $\frac{n(3n-k)}{4}$ (using the fact that $3n-k>0$). The number of matches between the two sets $P_1,\cdots ,P_k$ and $Q_1,\cdots ,Q_{3n-k}$ is at most $k(3n-k)$ games. Consequently, the total number of matches $N$ satisfies: $$N<\frac{nk}{4}+\frac{n(3n-k)}{4}+k(3n-k)\le \frac{3n^2}{4}+\frac{9n^2}{4}=3n^2,$$ which contradicts the given condition. Therefore, the assumption of proof by contradiction is incorrect, and the original proposition is true. $\square$