Problem 770

Let's consider the general case: let the number of participants be $n$, and the champion wins $k$ matches. There was no tie for the lead, so each of the others won at most $(k-1)$ times. The number of matches, counted from the winners' perspective, is therefore at most $k+(n-1)(k-1)$. In a round-robin tournament with $n$ participants, where everyone plays everyone else, the number of matches is $\frac{n(n-1)}{2}$. This means that

$$\begin{gathered} \frac{n(n-1)}{2} \leqq k+(n-1)(k-1), \text { hence } \\ \frac{n+1}{2}-\frac{1}{n} \leq k \end{gathered}$$

The smallest integer $k$ for which (2) holds is $\left[\frac{n}{2}\right]+1$, so the champion must win at least $\left[\frac{n}{2}\right]+1$ matches. This can indeed happen, for example, as follows: Let the participants stand in a circle, and each player defeat the $\left[\frac{n}{2}\right]$ players standing to their left, if they haven't already defeated them. This way, everyone plays everyone else, each player wins at most $\left[\frac{n}{2}\right]$ matches, and there is one, for example, the one to whom we first assigned the defeated players, who wins exactly that many. Change one of their lost matches to a win. This way, they become the champion with $\left[\frac{n}{2}\right]+1$ wins.

According to the above reasoning, for $n=10$ and $n=11$, the tournament winner must have won at least 6 matches, and there is indeed a possible outcome of the tournament where 6 wins are sufficient for the first place.

Remarks. 1. Many did not prove that it is possible for the tournament to have an outcome where someone wins with 6 victories, i.e., that the lower bound for the number of the champion's wins is sharp.

2. It can be seen that if ties for the lead are allowed, then 5 wins may be sufficient to win the tournament.