Curious case of Lewis Carrol, tournament runner ups and sorting

No less than four grand slams are played every year to find the best tennis player in the world. These are knockout tournaments in which, at each stage half of the players lose and get out. Two [supposedly] best players clash in the finals and the winner of that game is declared the champion (the best player) and the loser the runner up (the second best player). All is fine with our champion but there is just a small problem with our runner up: He might not be the second best player of the tournament.

How?

Let us assume that there were 16 players in the beginning with seedings 1 to 16, 16 being the best. Consider the following results for the matches in the tournament

15
	15
1
		15
5
	9
9
			16
12
	16
16
		16
4
	4
3
				16
11
	11
6
		11
7
	10
10
			14
2
	8
8
		14
13
	14
14

As expected, 16 is the winner but the runner up is 14 not 15. 15 crashed out in the semi finals playing against the champion.

So what can we conclude from this?

  1. Runner up may not be the second best player of the tournament.
  2. log n matches are required to decide the best player in the tournament.
  3. We can find the second best player in the tournament looking at the match results of the winner which is a list of log n players. At some point he must have defeated the second best player.

Here is a program that gives you the second best player in (n - 1) + ((log n) - 1) = n + (log n) - 2 comparisons:

Could not embed GitHub Gist 1173103: API rate limit exceeded for 103.115.8.6. (But here's the good news: Authenticated requests get a higher rate limit. Check out the documentation for more details.)