Let's say I have 10 teams competing in a round-robin tournament. Ties are not allowed, and only teams that have at least 7 wins can move on to a new tournament. How would I go about proving the maximum number of teams that could reach 7 wins and move on?
Determine maximum remaining teams in a round robin tournament
discrete mathematicsgraph theory
Related Solutions
This is almost the definition of a "$1$-factorization of $K_{2k}$", except that a $1$-factorization has an unordered set of matchings instead of a sequence of rounds. Since there are $2k-1$ rounds, this means that there are $(2k-1)!$ times as many tournaments, according to the definition above, as there are $1$-factorizations.
Counting $1$-factorizations of $K_{2k}$ seems to be a nontrival problem; see the Encyclopedia of Mathematics entry. The number of $1$-factorizations of $K_{2k}$ is OEIS sequence A000438. Also, see this paper (also here) for a count in the $k=7$ case.
Your approach to the first question is entirely reasonable. Since $5\cdot6=30>28$, it’s clear that $6$ wins guarantee advancement. To show that $5$ do not, we need only show that it’s possible for $5$ teams to win $5$ matches each; the arrangement shown by user73985 works fine and is natural enough that it’s the first one that I found as well. (You can complete it by distributing the remaining $3$ wins within the group consisting of teams $6,7$, and $8$; for example, you could have team $6$ beat teams $7$ and $8$, and team $7$ beat team $8$.)
For the second question, suppose that a team has $3$ wins; is it possible that it could advance to the second round? Suppose that teams $1,2$, and $3$ beat each of the higher-numbered teams: team $1$ beats everybody else, team $2$ beats everyone else except team $1$, and team $3$ beats everyone else except teams $1$ and $2$. That accounts for $18$ wins, leaving $10$ to be determined. Team $4$ beats teams $5,6$, and $7$, for $3$ wins, leaving $7$ wins to still to be distributed amongst teams $5,6,7$, and $8$. We want team $4$, with its measly $3$ wins, to make it to the second round, so we’ll try to split the remaining $7$ wins $2,2,2$, and $1$ amongst teams $5,6,7$, and $8$. Team $4$ did not beat team $8$, so team $8$ beat team $4$ and already has one win; we can give it another against team $5$. Now it must lose to teams $6$ and $7$, so they now have one win apiece. We can finish up by letting team $5$ beat team $6$, team $6$ beat team $7$, and team $7$ beat team $5$. To sum up:
- Team $1$ beats teams $2,3,4,5,6,7,8$.
- Team $2$ beats teams $3,4,5,6,7,8$.
- Team $3$ beats teams $4,5,6,7,8$.
- Team $4$ beats teams $5,6,7$.
- Team $5$ beats team $6$.
- Team $6$ beats teams $7,8$.
- Team $7$ beats teams $5,8$.
- Team $8$ beats teams $4,5$.
Thus, it’s possible to make it into the second round with just $3$ wins.
With only $2$ wins, however, it’s impossible to guarantee getting to the second round. The top three finishers cannot have more than $18$ wins altogether (either $7+6+5$ or $6+6+6$). That leaves $10$ wins amongst the remaining $5$ teams, so either each of the bottom $5$ teams has $2$ wins, or one of them has at least $3$ wins. In neither case is a team with just $2$ wins assured of getting into the second round.
There is some ambiguity in the situation in which each of the bottom $5$ teams wins $2$ matches. (This can happen, e.g., if teams $1,2$ and $3$ all beat each of teams $4,5,6,7$, and $8$, team $4$ beats teams $5$ and $6$, team $5$ beats teams $6$ and $7$, team $6$ beats teams $7$ and $8$, team $7$ beats teams $8$ and $4$, and team $8$ beats teams $4$ and $5$.) In this case the rules as given in the question don’t specify what happens. Some of the possibilities are: that only the top three teams go to the second round; that there is a playoff for the fourth position; that the fourth position is chosen randomly; or that the fourth position is decided by some tie-breaker like goal differential. As long as four teams always move on to the second round, it’s still possible for a team with just $2$ wins in the first round to move on, but if that does happen, other teams with $2$ wins fail to move on.
Best Answer
I don't really know too much about combinatories, but I found a solution!
45 games are played in total, so I would go this way to get some upper bounds:
We first assume that 7 teams qualify, but this would require the sum of wins from those 7 teams to be at least 49, which cannot happen.
Therefore, the soutuion has to be 6 or less, but 6 is also out of the question, since the other 4 teams play 6 games among themselves, so the sum of the top 6 teams has to be 39 or less.
So we are left with 5 at best, where 5 teams can get at most 35 wins, and... there is a concrete solution!
Teams A,B,C,D and E beat every game against teams F,G,H,I and J.
A beats B and C,
B beats C and D,
C beats D and E,
D beats A and E,
E beats A and B
Teams A,B,C,D and E have 7 wins each!
I am not exactly sure how this reasoning generalizes, though!