Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A single elimination tournament is performed in rounds. In each round the teams each play exactly one game and the winners continue, and the losers are knocked out of the competition. So, in each round, exactly half of the teams are eliminated. At the completion of the tournament, there is one winner who is undefeated. Assuming that when two teams play each other the outcome is always the same and assuming transitivity (i.e. A beats B and B beats C implies A would beat C), how many more games would have to be played to always find a second place winner?

What I don't understand is the transitivity rule, if A beats B wouldn't B be knocked out of the competition completely, how can he even have a change to beat C? Am I missing something. I started by creating a tree for 4 players A, B, C, and D when A beats B, I cross B which mean he can't play with anyone else anymore.

share|improve this question
    
I believe that to determine the second place winner, all players except the winner will play another tournament with the rules mentioned (the outcome is always the same and transitivity). Is that right? I'm not familiar with knock out competitions? –  user2038833 Feb 4 '13 at 8:58
2  
They don't really mean second place winner, they mean second best team. –  André Nicolas Feb 4 '13 at 9:00
    
Go back a little bit to the semi-finals. Let's say the four teams are A, B, C and D. Suppose A beats B, C beats D, and A beats C. Now we know A is the winner. The second best team can only be B or C. So you let B compete with C. Whoever wins will be the second best. –  Tunococ Feb 4 '13 at 9:09
2  
@Tunococ Why can't the second best team be the one beaten by A in round one? –  mrf Feb 4 '13 at 9:13
    
@mrf You're right. I didn't think it through. Joriki's answer is correct. –  Tunococ Feb 13 '13 at 14:02
add comment

2 Answers

The rule doesn't refer just to games within the tournament, but to any potential games between $A$ and $B$ and between $B$ and $C$. Also it's not to be interpreted in chronological order; it doesn't matter whether $A$ first beats $B$ or $B$ first beats $C$, so you can have $B$ beat $C$ in the tournament, and then at a later stage you can have $A$ beat $B$. The rule tells you that in this case you don't need to let $A$ play $C$ to establish that $A$ is better than $C$; you can infer it from those two games already played.

To answer the question itself, note that the potential candidates for second place are exactly the players eliminated by the winner.

share|improve this answer
    
Assuming N is the number of players, the winner will beat $log_{2}N$. The second tournament will have at most $log_{2}N-1$ games but since there is the transitivity rule suppose this number should be lower. How would I keep track of who beat who, isn't it up to chance? –  user2038833 Feb 4 '13 at 9:11
    
that's exactly what I'm doing. A single elimination tournament of k players requires k-1 games. –  user2038833 Feb 4 '13 at 9:35
    
@user2038833: I'm sorry, you're right of course; I've removed that comment. About the transitivity rule: It's not like you have to invoke that somehow in addition to the single-elimination principle; it's just there to allow you to conclude that single elimination is sufficient to find the best player (or in fact to make it well-defined to speak of a "best player"). –  joriki Feb 4 '13 at 9:36
add comment

So there is a(n unknown) ranking of the teams, no ties. The single-elimination tournament tells you who is the first in the ranking. The question appears to be, how many more matches do you need to determine the second one in the ranking.

The only candidates are those who have lost to A, because all the others have lost to some other team, and thus are at most third behind A and this other team. You can then play a single-elimination tournament among those who have lost against A to determine who's best among them.

If the number of teams is $n$, then A has played $\lceil \log_2(n) \rceil$ games (or one less if he got a bye in the first round), so I think you need the $\lceil \log_2(n)\rceil - 1$ matches among those teams (one less if A got a bye in the first round).

share|improve this answer
    
@AndreasCaranti But wouldn't that just be a normal single-elimination tournament, without the transitivity rule? I agree that there is at most $⌈log_{2}(n)−1⌉$ but what's the exact number? –  user2038833 Feb 4 '13 at 9:23
    
@user2038833: What's this contrast you're drawing between a "normal" single-elimination tournament and the transitivity rule? I'm wondering whether this might be based on a misunderstanding of the problem. –  joriki Feb 4 '13 at 9:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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