# Pre-interview_Test_Question_41

if you draw a tree, say for N=3 (8 teams) or something, it’ll become obvious
when you have 2^N teams, the first round will involve some number of games (each where 2 of each of these teams are playing each other, so that there are \dfrac{2^N}{2}=2^{N-1} games. in the second round there will be \dfrac{2^{N-1}}{2}=2^{N-2}.
in general, in the k th round there will be 2^{k-1} games.
the competition will end when there are 2 teams in the final (which must also be included as a game ofc), so we need to sum all of the games in all rounds up to this point for the total.

\begin{align} \therefore \sum_{k=0}^{N-1}2^k&=\frac{1(2^{(N-1)-(0)+1}-1)}{2-1} \\&=2^N-1 \end{align}

i think the second part is a little vague, i explain the approach that makes the most sense to me (putting aside the fact they have come in second place having lost the final, and so are conventionally second best).
assuming the second best team isn’t automatically the team in second place, i think that all the remaining teams that had been defeated by the best team beforehand must play amongst each other. this is because if the second best team had played against the best team in the midst of the tournament, they will definitely have been defeated. however, we cannot know for certain whether or not this team will have defeated the second PLACE team in a match (they could not have played a match together, due to the binary setup of the tournament. draw a tree for n=3 and notice how there are 2 distinct “halves” in each of which the group of players playing are distinct). if all teams defeated by the best team play amongst each other then it will take into account the possibility that the second place team may not have been able to defeat the another.
the best team will have defeated 1 team per round in the competition, and there will have been \log_2(2^N)=N rounds. so the best team will have played against N teams. so a minimum of N-1 extra games are required as A_1 plays A_2, winner plays A_3, \ldots, winner of (A_{N-2} vs. A_{N-1}) plays A_N.

1 Like

One of my favourite questions so far

1 Like

that’s fair enough, personally i didn’t like the second part as much mainly due to how vague it seemed. initially the logic also seemed sort of unintuitive to me lol (would you agree with the answer?)