There were $n\ge2$ teams in a tournament. Each team played against every other team once without draws. A team gets 0 points for a loss and gets as many points for a win as its current number of losses. For which $n$ all the teams could end up with the same number of points?
Problem
Source: Kyiv mathematical festival 2019
Tags: Kyiv mathematical festival, combinatorics
10.05.2019 08:09
Each team plays exactly $n-1$ matches. First we prove that $n-1$ is even hence $n$ is odd. Suppose if works for an even $n$. Then a team $t_i$ plays an odd number of matches ($n-1$ matches). Therefore, the team $t_i$ must have more wins than losses or more losses than wins. In both cases, there must exist a team with more losses than wins or more wins than losses, respectively. If there does not, then every team has more losses than wins, or vice versa, a contradiction. Now if $n$ is odd, any team $t_i$ can win an equal no. of matches as it loses, with the total point count is $\sum_{k=1}^{\frac{n-1}{2}}k=\frac{(\frac{n-1}{2})(\frac{n-1}{2}+1)}{2}$. $n$ is odd is a necessary condition, now we prove that it is sufficient by induction. $n=3$ is trivial. Assume for $n=2k+1$ that it works. Every team has the same number of points. Now we add $2$ new teams, $t_{2k+2}$ and $t_{2k+3}$. We let $t_{2k+2}$ win any $k+1$ matches and lose to $t_{2k+3}$ and also let $t_{2k+3}$ win any $k$ matches apart from $t_{2k+2}$. Now both new teams have won and lost the same amount of matches, so they have the same points and we are done.
13.05.2019 09:31
Clarification: the result of each team is a string of letters "W" and "L". For example, string "WWLWLLLWLW" gives 0+0+1+4+5 points.