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

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

Tags:

Graph Theory

Related

Solving a Fractional Equation Involving a Logarithm Proof of Bound for Growth of Divergent Trajectory in $3x+1$ Problem Evaluate $\frac{9}{1!}+\frac{19}{2!}+\frac{35}{3!}+\frac{57}{4!}+\frac{85}{5!}+......$ What exactly is topology? Show that $\int_{0}^{\pi/2} \frac{\sin x~dx}{1+\sin 2x}=\frac{\coth^{-1} \sqrt{2}}{\sqrt{2}}$ How are $SU(n)$, $SL(n)$ and $\mathfrak{sl}(n,\mathbb{C})$ related? Evaluate using Stokes' Theorem A proper subspace of a normed vector space has empty interior clarification proof that $\frac{a_{4n}-a_2}{a_{2n+1}}$ : integer Are the real eigenvalues of real symmetric matrices continuous? Let $A=\begin{bmatrix} 1 & 2\\ 3& 4 \end{bmatrix}$ then det$(A^3-6A^2+5A+3I)=3$ If $h(n+1)=h(n)+3$ and $h(0)=1$ , give an explicit expression for $h(n)$ without "guess" $h(n)=3n+1$ first .

Recent Posts