# Finding the minimum wins in a round-robin tournament.

There are 16 teams in total. They are divided into two groups of 8 each. In a group, each team plays a single match against every other team. At the end of the round, top 4 teams go through to the next round from each group. Assume, a match can only result in either a win or a loss and never a tie.1 win=1 point; 1 loss=0 point.

Questions

1.What is the minimum no. of wins needed for a team in the first stage to guarantee its advancement to the next round?

2.What is the highest no. of wins for a team in the first round in spite of which it would be eliminated at the end of the first stage?

3.What is the minimum number of wins that may allow advancement to the second round?

The way i approached the question is like this:

There will be 28 matches each within the two teams. After that I started distributing the points by hit and trial. I know that there are 28 match points. But, say for question 1, can we say that $28=5*5+3$. So 5 teams with 5 winning each creating ambiguity? So, the minimum possible wins that will always guarantee is $5+1=6$. wins. But then I started distributing match points to the teams and found 5 points 5 times is not possible. How to get the answer logically and quickly?

PS: The answer given is 6(Q 1) and 2 (Q 3).

## 2 Answers

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 get 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.

• "With only 2 wins, however, it’s impossible to get to the second round" - this phrasing seems to contradict the last sentence of the answer, which says "it’s still possible for a team with just 2 wins in the first round to move on". As your answer explains, it's possible for a 2-wins team to progress, but it is not guaranteed. My suggested edit was rejected, but I believe it should read something similar to "with only 2 wins, however, it’s not possible to guarantee progression to the second round." – Spinner May 27 at 13:32

5 points 5 times is possible. Call the teams 1, ..., 8. Teams 1-5 all beat all of teams 6-8, and then:

Team 1 beats teams 2 and 3

Team 2 beats teams 3 and 4

Team 3 beats teams 4 and 5

Team 4 beats teams 5 and 1

Team 5 beats teams 1 and 2