# Combinatorics olympiad problem

Twenty-five tennis players are numbered by the numbers $1,2,...,25$. The players are divided into five teams with five players on each team in such a way that the sum of the numbers of the players on each team equals $65$. At a tournament each player plays matches against all other players except those included in his/her own team. After the tournament it turns out that all matches were won by the player with higher number. We say that team $X$ wins against team $Y$ if the players on team $X$ won more matches than they lost against the players on team $Y$. Prove that there exist three teams $A,B,C$, such that $A$ wins against $B$, $B$ wins against $C$, $C$ wins against $A$

• If I understand this correctly, between the members of team $A$ and team $B$ there are $25$ matches, and if $A = \{1, 2, 13, 24, 25\}$ and $B = \{3, 14, 15, 16, 17\}$, then the score between the two teams is $11$ to $14$ in $B$'s favour. Am I right? – Arthur Oct 1 '15 at 12:31
• Yes that would be correct, so $B$ wins – guest Oct 1 '15 at 12:33
• This is from the qualifying round of the Swedish math olympiad this year, correct? – A.Sh Oct 1 '15 at 12:34
• Yes, you are correct – guest Oct 1 '15 at 12:39
• Ok, just checking if my hunch was correct :) Are you too impatient to wait the few weeks necessary for them to publish the solutions? – A.Sh Oct 1 '15 at 12:42

## 1 Answer

Consider the underlying directed graph, where $X \to Y$ if and only if $X$ beats $Y$. The only way that there is no directed triangle is if there is a total ordering, in particular, if there is a team which wins against all other teams.

Now I show that every team must lose at least once. For each element $X$, let $v(x)$ be the number of victories that it scores across all matches. For a team $S$, let $v(S)$ be the sum of $v(x)$ over $x \in S$.

Then we see that for each team $v(S) \leq 65-5-10=50$. (An element $k$ can score at most $(k-1)$ victories, and we can subtract the 10 victories within the elements of $S$). This means that against one of the other 4 teams, $S$ must score at most 12, and hence $S$ must lose at least once.