4
$\begingroup$

I know there are many questions/answers about single elimination tournaments out there, but I wanted to approach this question in a more holistic way.

For a single-elimination tournament with N teams, if N-1 games are needed to determine a winner, how many more games are needed to determine the second best team with the same number (N) of players?

Additionally, how many ROUNDS are needed to determine a winner for every N?

These answers should probably be in an equation or expression form to apply to an infinite N. Good luck!

$\endgroup$
3
$\begingroup$

Disclaimers and assumptions

Since this is posed as a calculation puzzle, and there's no need to produce an acceptable or even justifiable tournament system for real world tournaments, I'm going to go on ahead and assume that "X wins Y" is both deterministic and transitive, and that drawn games are not a thing that exists.

To make it clear, the tournament system I'm describing is only justifiable for a game, where the $N$ participants are assigned a unique hidden number from $1$ to $N$ at the start, and a match consists of comparing the numbers.


Finally, to the point.

First, let's prove the claim that a knockout tournament of $N$ participants takes $N-1$ games. It's mighty simple: in the end, everyone must have lost a game, except the winner. Each game produces one loss. Q.E.D.


Minimal number of rounds that can guarantee finding the winner

On the final round, if we need to guarantee finding the winner, we can have at most two players without losses. On the round before that, at most 4. On the round before that, at most 8, and so on. The maximum number of participants doubles for each additional round.

Therefore, a knockout tournament with $N$ participants can guarantee finding a unique winner in

$\left \lceil{\frac{log(N)}{log(2)}} \right \rceil$ rounds. (The strange brackets are the ceiling function, meaning "rounded up")


Second place

The number of rounds also happens to be exactly the number of participants the winner of the tournament has knocked out. (If $N$ isn't a power of 2, it's the worst case scenario, anyway.). Since anyone knocked out by someone that's not the winner cannot be eligible for second place, it's enough that those knocked out by the winner play another knockout tournament among themselves. This takes

$\left \lceil{\frac{log(N)}{log(2)}} \right \rceil -1$ games,

because none of the required games have yet been played. This is easily proven: if such a game had been played, one of the participants would have been knocked out by the other one, and not by the winner.


All summed up

Therefore, finding the first and second places takes a total of

$N + \left \lceil{ \frac{log(N)}{log(2)} } \right \rceil -2$ games.

Which for some sample values of N are

2 participants: $2 + \left \lceil{ \frac{log(2)}{log(2)} } \right \rceil -2 = 1$ game
3 participants: $3 + \left \lceil{ \frac{log(3)}{log(2)} } \right \rceil -2 = 3$ games
4 participants: $4 + \left \lceil{ \frac{log(4)}{log(2)} } \right \rceil -2 = 4 $ games
10 participants: $10 + \left \lceil{ \frac{log(10)}{log(2)} } \right \rceil -2 = 12 $ games

$\endgroup$

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.