1
$\begingroup$

Here is a problem from a math competition - the solution of which requires the enumeration of combinations. I am asking for affirmation of my solution.

Twenty teams are in a round-robin tournament; each team plays every other team exactly one time. What is the biggest number of teams that could have at least $16$ wins?

Solution

There are a total of ${}_{20}C_{2} = 190$ games played in the tournament; there are $190$ wins and $190$ loses. Since $(12)(16) = 192$, less than twelve teams in the tournament can win $16$ games. If the outcome of a tournament includes a team $A$ with more than $16$ wins, one of which came at the expense of another team $B$, the outcome of another tournament that is identical to the first except that team $A$ loses its game with team $B$ would have at least as many teams with at least $16$ wins. So, the outcome of a tournament with the biggest number of teams with at least $16$ wins is one in which no team has more than $16$ wins.

If the outcome of a tournament were to have exactly eight teams with $16$ wins, among them they would have a total of $24$ loses. As there are twelve other teams, each team with $16$ wins would have to defeat four other teams with $16$ wins, but this would give $(4)(8) = 32$ loses among them. This is a contradiction. Eight teams cannot have $16$ wins.

The outcome of a tournament can have seven teams with exactly $16$ wins. Each of the teams with $16$ wins could have won all $13$ games against the teams with less than $16$ wins and half of their games among those teams that finished with $16$ wins. Each of the remaining teams can win six games against each other.

$\endgroup$
  • $\begingroup$ What is your question? The first paragraph of the solution, while correct, is not needed. $\endgroup$ – Ross Millikan May 4 '16 at 23:37
  • $\begingroup$ @Ross Millikan In the first paragraph, I show that I can simply discuss cases in which the most wins any team gets is 16 in order to determine the biggest number of teams that can win at least 16 games in the tournament. $\endgroup$ – user232552 May 5 '16 at 0:33
0
$\begingroup$

Your analysis is correct

In general with $N$ teams playing each other once, the largest number $k$ of teams that can win at least $m$ games can be found by considering the average number the $k$ can win among themselves and the number they can win against the others so $\dfrac{k-1}2+(N-k) \ge m$ which implies $$k \le 2N-2m-1$$

In your example with $N=20$ and $m=16$ this gives $k \le 40-32-1=7$ as you found

This also shows the maximum will always be odd

$\endgroup$
  • $\begingroup$ May you give me a reference to this? $\endgroup$ – user232552 Aug 10 '16 at 22:34
  • $\begingroup$ Why do you need a reference? Your analysis is logically correct, as is my generalisation. It may or may not be original, but that is not particularly important. $\endgroup$ – Henry Aug 10 '16 at 23:33
  • $\begingroup$ Oh yeah, I appreciate your comments. $\endgroup$ – user232552 Aug 10 '16 at 23:59
  • $\begingroup$ A reference may put this problem in context. $\endgroup$ – user232552 Aug 10 '16 at 23:59

Your Answer

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