4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – herb steinberg Jun 27 at 0:56
  • $\begingroup$ Should the phrase "among all $n$ teams" in your lead paragraph have been instead "among all $2n$ teams"? $\endgroup$ – hardmath Jun 27 at 1:31
  • $\begingroup$ 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. $\endgroup$ – Vk1 Jun 27 at 3:07
  • 2
    $\begingroup$ herb's example works for any $n$, so $n$ wins is never sufficient. It would suffice to show $n+1$ is sufficient. $\endgroup$ – Fimpellizieri Jun 27 at 3:13
  • $\begingroup$ 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. $\endgroup$ – Vk1 Jun 27 at 3:17
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Vk1 Jun 27 at 4:40
  • $\begingroup$ My edit addresses with some more generality these estimations. $\endgroup$ – Fimpellizieri Jun 27 at 4:44
  • $\begingroup$ Thanks.. those edits were quite helpful. $\endgroup$ – Vk1 Jun 27 at 5:58
  • 1
    $\begingroup$ I have edited with what should hopefully be a clear proof of the exact minimum. $\endgroup$ – Fimpellizieri Jun 27 at 6:05
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Fimpellizieri Jun 27 at 5:06
  • $\begingroup$ Oops. I seem to have botched my arithmetic, I'll fix it. Thanks for pointing out the error! $\endgroup$ – im_so_meta_even_this_acronym Jun 27 at 5:08
  • $\begingroup$ @Fimpellizieri is this better? $\endgroup$ – im_so_meta_even_this_acronym Jun 27 at 5:13
  • $\begingroup$ 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? $\endgroup$ – Vk1 Jun 27 at 6:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.