single elimination tournament, don't understand question?

Question

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.

Answer 1

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.

Answer 2

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