Results 1 to 4 of 4

Math Help - Knockout

  1. #1
    Member
    Joined
    Apr 2009
    Posts
    190

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by Aquafina View Post
    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 2^n-1 match: it is the one that loses to the champion!

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Apr 2009
    Posts
    190
    Quote Originally Posted by tonio View Post
    I think (i) is correct but imo (ii) is zero since the second best team is determined in the 2^n-1 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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Hell Aquafina
    Quote Originally Posted by Aquafina View Post
    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 2, 4, 8, ... teams before each round is played. There will therefore be N rounds altogether for 2^N teams.

    You can work out the number of games by summing a GP:
    1+2+4+...+2^{N-1}=2^N -1
    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 N matches, this means that the second best team is one of the N 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 2. 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 N teams to start with, we must eliminate (N-1) of these to get a winner.

    So we shall need (N-1) games! It's as easy as that.

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

    Grandad
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum