There's a counterexample with 8 teams: A, B, C, X, Y, Z, M, S
- S wins against M
- M wins against A, B, and C
- A wins against Y and Z
- B wins against Z and X
- C wins against X and Y
- X wins against M and A
- Y wins against M and B
- Z wins against M and C
- Everything else ties.
Teams ABCXYZ each win twice and lose twice for a score of $2\times0+3\times1+2\times3=9$.
Team M wins against ABC and loses to XYZS, for a score of $4\times0+0\times1+3\times3=9$.
Team S wins once and ties 6 times, for a score of $0\times 0+6\times1+1\times3=9$.
How I found this: First, for easier counting I changed the rules by subtracting $n-1$ points from each team such that ties give $0$ points, and wins and losses each $2$ and $-1$. That makes it easier to see which possible combinations of wins and losses add up to the same. Then I'm looking for a directed graph with no 2-loops such that the value of each node is the same.
Since there are as many wins as losses, in a counterexample there must be at least one team that win more times than they lose. But that team cannot possibly have less than $2$ points, so let's see which way we can make a node with value 2: They are: $1W+0L$, $2W+2L$, $3W+4L$ and so forth -- so if we have one of $1W+0L$ and $3W+4L$ the number of wins/losses add up right.
From there it was just a matter of puzzling out where to add $2W+2L$ nodes to the graph such that we don't need more than one match to take place between the same two teams.
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
Maximum number of wins with which a team may not qualify: $10$
The idea here is to list all the teams in order of their number of wins, and maximize the $5$th best team's wins.
Hence we want as many total wins as possible for the top $5$ teams - meaning we want the least total possible wins for the bottom three teams. What is this least number? Well each of these three teams must play each other in a total of $6$ games, so together they account for a minimum of $6$ wins. The total number of games is $56$, so the top $5$ teams get to distribute $56-6=50$ wins. Now the best that the $5$th best team can therefore achieve is $\frac{50}{5}=10$ wins. Note that this is possible if each of the top $5$ teams always beats the bottom $3$ teams ($6$ wins) and then wins exactly one match against the other top teams ($4$ wins) - giving a total of $10$ wins to the $5$-th best team. Hence $10$ is the most number of wins which does not guarantee qualification (though this is an extremely rare case).
Minimum number of wins to qualify: $4$
The idea here is to apply the same procedure and look at the performance of the $4$-th best team. Each of the bottom $5$ teams must play each other - giving them $20$ total victories to distribute. Hence the $4$-th best person must have at minimum $\frac{20}{5}=4$ victories. This is again achievable - each of the bottom $5$ teams wins exactly once against each other and looses all other matches.