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?

Let $N$ be the number of teams. One needs to play $\lceil \log_2 (\log_2 N) \rceil$ 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. So, because we need to distinguish between $\log_2 N$ possibilities, information theory says that we need at least $\lceil \log_2 (\log_2 N) \rceil$ bits of information. Each game only gives us one bit, so this is a lower bound on how many additional games we need to play. This lower bound is achievable by running another binary-tree-style tournament among those $\log_2 N$ potential teams.