# What is the minimum wins needed to be in top 50 percent of teams in a round robin tournament?

Consider a championship among $$2n$$ teams. The first round of the championship consists of a round robin tournament among all $$2n$$ teams. The top $$n$$ teams progress to the next round. Ties are resolved (by coin toss or some other parameter) only when multiple teams are fighting for the $$n^{th}$$ slot.

How many wins would be "sufficient" for a team to guarantee that it reaches the next round of the championship?

Alternatively, what are the number of wins that a team needs, so that it doesn't need to worry about the results of the games between the rest of $$2n-1$$ teams?

My intuition and observations:-

A semi-regular tournament on $$2n$$ vertices would have $$n$$ vertices with $$n-1$$ outdegree(wins) and $$n$$ vertices with $$n$$ outdegree(wins).

Thus $$n-1$$ wins is not sufficient.

I guess that any team with $$\geq (n+1)$$ wins is guaranteed a slot in the next round of the championship?

• Ties can create problems. Example four teams. One team loses all three games. Each of the others ends up with two wins and one loss. (note: your statement has an error - you need to say round robin among 2n teams,) Also your statement doesn't say how many teams go onto the next round - usually it would be half, but without that provision, my example is meaningless. – herb steinberg Jun 27 at 0:56
• Should the phrase "among all $n$ teams" in your lead paragraph have been instead "among all $2n$ teams"? – hardmath Jun 27 at 1:31
• Corrected.I agree that ties can cause problems. So in your example 2 is not sufficient but 3 wins is definitely sufficient. That is the answer I am looking for. Thus when the round robin is among 4 teams, 3 wins is sufficient but 2 wins is not sufficient to guarantee a slot in the next round. – Vk1 Jun 27 at 3:07
• herb's example works for any $n$, so $n$ wins is never sufficient. It would suffice to show $n+1$ is sufficient. – Fimpellizieri Jun 27 at 3:13
• Now that you have mentioned, I realised that a tournament on $2n$ vertices can be organised in such a way that $n$ teams have $n-1$ wins and $n$ teams have $n$ wins. So yes, $n-1$ is not sufficient. I wonder how to prove the second part of your claim. – Vk1 Jun 27 at 3:17

When $$n+1$$ is not sufficient, we'll have at least $$n+1$$ teams with score of at least $$n+1$$. That means there will have been a total of at least $$(n+1)^2$$ games, so we need

$$(n+1)^2 \leqslant \binom{2n}2 \implies n\geqslant 4.$$

Already for $$n=4$$ we can find one such configuration.

Choose $$5$$ of the teams and have each of them beat all of the other $$3$$. Additionally, arrange these $$5$$ chosen teams in an oriented circle and have each of them beat the next $$2$$.

In this way, the $$5$$ chosen teams will each have a score of $$5$$, while the other $$3$$ teams will each have a score of at most $$2$$.

More generally, this can be adapted to show that no given $$n+k$$ works when $$k$$ is independent of $$n$$.

For a given $$k$$, let $$n$$ be sufficiently large. We've already seen that we need $$(n+k)^2 \leqslant \binom{2n}2$$, but we'll see that the circle arrangement demands another condition.

Choose $$n+k$$ of the teams and have each of them beat all of the other $$n-k$$. Additionally, arrange these $$n+k$$ chosen teams in an oriented circle and have each of them beat the next $$2k$$. This requires that

$$2k \leqslant \frac{(n+k)-1}2 \iff 3k+1 \leqslant n$$

This ensures that $$n+k$$ of the teams will each have a score of at least $$n+k$$, while the other $$n-k$$ will have a score of at most $$n-k-1$$.

I'll try and make im_so_meta's answer more precise.

Claim: The minimum number of wins is $$\lfloor 3n/2\rfloor$$.

Proof: First, suppose that achieving a score of $$\lfloor 3n/2\rfloor$$ did not guarantee that a team will be above the $$50$$th percentile. Then there would be some win-loss configuration for which $$n+1$$ teams each had a score of $$\lfloor 3n/2\rfloor$$ or more. All of these wins would have taken at least

$$(n+1)\left(\frac{3n}2-\frac12\right) = \frac{3n^2+2n-1}2$$

games. The other $$n-1$$ teams will have played another

$$\binom{n-1}2 = \frac{n^2-3n+2}2$$

games amongst themselves, for a total of $$2n^2 - (n-1)/2$$. But this is more than $$\binom{2n}2 = 2n^2 - n$$, which is the total number of games, so no such configuration exists. It follows that achieving a score of $$\lfloor 3n/2\rfloor$$ does guarantee that a team will be above the $$50$$th percentile.

We now show that it's possible to achieve $$\lfloor 3n/2\rfloor - 1$$ without being above the $$50$$th percentile.

## Case $$(1):$$$$n$$ is even

In this case, $$\lfloor 3n/2\rfloor - 1 = 3n/2 - 1$$. Write this as $$(n-1) + n/2$$.

Choose $$n+1$$ of the teams and have each of them beat all of the other $$n-1$$. Additionally, arrange these $$n+1$$ chosen teams in an oriented circle and have each of them beat the next $$n/2$$. Notice that here there is no freedom, and this completely determines the games amongst these teams.

This ensures that $$n+1$$ of the teams will each have a score of exactly $$(n-1) + n/2$$, while the other $$n-1$$ teams will each have a score of at most $$n-2$$.

## Case $$(2):$$$$n$$ is odd

In this case, $$\lfloor 3n/2\rfloor - 1 = 3n/2 -1/2 -1$$. Write this as $$(n-1) + (n-1)/2$$.

Choose $$n+1$$ of the teams and have each of them beat all of the other $$n-1$$. Additionally, arrange these $$n+1$$ chosen teams in an oriented circle and have each of them beat the next $$(n-1)/2$$. In this case, there is freedom to choose the outcome of diametrically opposite teams arranged in the circle.

This ensures that $$n+1$$ of the teams will each have a score of at least $$(n-1) + (n-1)/2$$, while the other $$n-1$$ teams will each have a score of at most $$n-2$$.

• Thank you for the counter-example. Thus $n+1$ is not always sufficient. In your example 6 wins is sufficient as at most 4 teams can have a score of 6 or higher. But my guess is that the correct answer is probably $n+c$, where $c$ is $O(1)$. – Vk1 Jun 27 at 4:40
• My edit addresses with some more generality these estimations. – Fimpellizieri Jun 27 at 4:44
• Thanks.. those edits were quite helpful. – Vk1 Jun 27 at 5:58
• I have edited with what should hopefully be a clear proof of the exact minimum. – Fimpellizieri Jun 27 at 6:05

@Fimpellizieri has already established $$n+1$$ is insufficient.

I claim that the minimum number of wins is $$\frac{3n}{2}$$. Assume for contradiction $$n+1$$ teams have this win total, then we already have $$\frac{3n^2+3n}{2}$$ wins logged in total by these teams, and the other $$n-1$$ teams must have at least $$\binom{n-1}{2}=\frac{n^2-3n+2}{2}$$ wins between them, for a total of $$2n^2+1$$. However, there are only $$\binom{2n}{2} = 2n^2-n$$ total wins! Oops. Contradiction.

Construction: Have $$n+1$$ of the people all beat the other $$n-1$$ people. Now, we can have all of the $$n+1$$ people have $$\frac{n+1}{2}$$ wins amongst themselves by putting them on a circle and having them beat the next $$\frac{n+1}{2}$$ people in a certain direction, plus or minus a half (half of the people have plus, half have minus) (credit to @Fimpellizieri for the idea). For those who have minus a half, then we have $$\frac{3n}{2}-1$$ wins, and all of these people tie.

I realize this answer glosses over the cases whether $$n$$ is even or odd, but the answer is either $$\frac{3n}{2}$$ or $$\frac{3n}{2}-\frac{1}{2}$$.

Thanks for @Fimpellizieri for pointing out that I accidentally found the equality case, botched the arithmetic, and somehow thought it was the answer.

• I think the general direction is good, but this definitely needs to be tidied up. In my example with $n=4$ we see that $3n/2 -1 = 5$ is not enough, and that in fact $n+1$ teams do achieve that win total. – Fimpellizieri Jun 27 at 5:06
• Oops. I seem to have botched my arithmetic, I'll fix it. Thanks for pointing out the error! – im_so_meta_even_this_acronym Jun 27 at 5:08
• @Fimpellizieri is this better? – im_so_meta_even_this_acronym Jun 27 at 5:13
• Thanks to both @Fimpellizieri and im_so_meta_even_this_acronym ... The proof shows that $3n/2$ is sufficient whereas $3n/2-1$ may not be sufficient as shown by the example. I guess we can resolve the problem to be closed? – Vk1 Jun 27 at 6:00