Fair Soccer Championship


I got this problem from Rustan Leino, who got it from Sergei Vorobyov.

I solved it and wrote up my solution.


The games played in the soccer world championship form a binary tree, where only the winner of each game moves up the tree (ignoring the initial games, where the teams are placed into groups of four, two of which go on to play in the tree of games just described). Assuming that the teams can be totally ordered in terms of how good they are, and a game is always won by the best team, the winner of the championship will indeed be the best of all of the teams. However, the second-best team does not necessarily come in second place in the championship. How many additional games need to be played to determine the second-best team?

Solution     Reveal