Thread: Knockout

i) How many games are played in a knockout competition involving 2^N teams?

ii) How many additional games are needed to determine the second best team?

My answers are:

i) 2^N - 1

ii) N-1

wanted to confirm these

Originally Posted by Aquafina

i) How many games are played in a knockout competition involving 2^N teams?

ii) How many additional games are needed to determine the second best team?

My answers are:

i) 2^N - 1

ii) N-1

wanted to confirm these

I think (i) is correct but imo (ii) is zero since the second best team is determined in the match: it is the one that loses to the champion!

Tonio

Originally Posted by tonio

I think (i) is correct but imo (ii) is zero since the second best team is determined in the match: it is the one that loses to the champion!

Tonio

Um no, consider 2 groups A and B, each with 2 people, i.e. 4 people in total, so N = 2.

The winner of Group A's match will compete with the winner of Group B's match. If the winner of Group A is the ultimate winner, then the winner of Group B should play the other player that was in Group A, as he may have been a better player.

Now consider this for larger values of N, each time one finalist will be from 1 half of the original set of people, and the other finalist from the other half. The loser of the final match should play the people in the other half now working backwards to determine who's the next best player.

Hell Aquafina

Originally Posted by Aquafina

i) How many games are played in a knockout competition involving 2^N teams?

ii) How many additional games are needed to determine the second best team?

My answers are:

i) 2^N - 1

ii) N-1

wanted to confirm these

You are right in both of your answers.

Part i)

Each round eliminates half the remaining teams. So, working back from the final there are teams before each round is played. There will therefore be rounds altogether for teams.

You can work out the number of games by summing a GP:

which is the answer you got. But see below for a simpler method.

Part ii)

Initially I thought your answer was wrong, but when I tried various numbers, I came to the conclusion you were right. So, how did I get that answer?

First, note that (assuming all the teams always play at their best, of course!) the second-best team will win against every other team except the eventual winner. So the winner will, at some stage, knock out the second best team. Since the winner plays matches, this means that the second best team is one of the teams who lose to the eventual winner.

I then started thinking about how to structure a knockout competition when we don't necessarily have a number of teams equal to a power of . This can lead to all sorts of complicated ways of arriving at the total number of games that will be played: summing a GP, using induction, recursion, ...

But the bottom line is this - and it's almost unbelievably simple! - a team can only be knocked out of a competition when it loses a game. And when it does lose a game, there is no point in that team playing another game. And if we have teams to start with, we must eliminate of these to get a winner.

So we shall need games! It's as easy as that.

So here's the easy answer to part (i): if you start with teams, you'll need games.

Grandad