2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Arthur Oct 1 '15 at 12:31
  • $\begingroup$ Yes that would be correct, so $B$ wins $\endgroup$ – guest Oct 1 '15 at 12:33
  • $\begingroup$ This is from the qualifying round of the Swedish math olympiad this year, correct? $\endgroup$ – A.Sh Oct 1 '15 at 12:34
  • $\begingroup$ Yes, you are correct $\endgroup$ – guest Oct 1 '15 at 12:39
  • 1
    $\begingroup$ Ok, just checking if my hunch was correct :) Are you too impatient to wait the few weeks necessary for them to publish the solutions? $\endgroup$ – A.Sh Oct 1 '15 at 12:42
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.