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

I solved it, wrote up my solution, and posted it on my website. Eight years later, Oriel Maxime emailed me that the solution was wrong (since I'd confused the round count with the game count). He also showed me how to correct it, and I've done that. Thanks, Oriel!

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?

Let $N$ be the number of teams. One needs to play $\log_2 N - 1$ additional games.

The reason is as follows. The team that winds up winning will have played $\log_2 N$ games, since it plays one game per round and each round eliminates half the teams. Any of the $\log_2 N$ teams that it beat in those games could be the second-best team.

We don't have any information from the tournament about the relative ordering of these $\log_2 N$ teams because their subtrees don't overlap. Thus, each additional game will only eliminate one team—the losing team—from contention for second-best. This means we need to play $\log_2 N - 1$ additional games. Of course, many of those additional games can be played in parallel by using a binary-tree tournament format.