Finding the Second-Best Player in Fewest Matches

The problem: $n$ tennis players enter a single-elimination tournament, every match eliminates the loser, and the last player standing is the best. Finding the winner takes exactly $n - 1$ matches, since every match eliminates exactly one player and $n-1$ players need to be eliminated. The follow-up question is the real puzzle: how many additional matches are needed to be certain who the second-best player is? Most people guess you need another full mini-tournament among everyone the winner beat, but there's a much cheaper answer.

The key insight: the second-best player only lost to the champion

Assume a strict ranking with no upsets, a better player always beats a worse one. Then the second-best player must have lost, at some point, directly to the eventual champion, because the only player who can beat the second-best is the best. Anyone the second-best player beat is by definition worse, so the second-best could only have been eliminated by the one player better than them. That means you don't need to check everyone the champion beat, only the players the champion personally faced during the bracket.

In a single-elimination bracket with $n$ players, the champion plays exactly $\lceil \log_2 n \rceil$ matches (one per round). So the second-best player is guaranteed to be among that small set of $\lceil \log_2 n \rceil$ opponents. Run a mini-tournament among just those opponents to find the best of them, using $\lceil \log_2 n \rceil - 1$ more matches.

Worked example: 8 players

With $n = 8$ players, finding the champion takes $8 - 1 = 7$ matches, arranged as a standard bracket: 4 matches in round one, 2 in round two, 1 final. The champion played exactly $\log_2 8 = 3$ matches, one per round. Those 3 opponents are the only candidates for second place. Run a mini-tournament among those 3: match two of them (1 match), then the winner plays the third (1 more match), 2 matches total to crown the second-best. Grand total: $7 + 2 = 9$ matches, versus the $\binom{8}{2} = 28$ matches a full round-robin would need, or the naive guess of re-running a mini-tournament among all 7 players the champion's side of the bracket ever beat.

The general formula is $(n - 1) + (\lceil \log_2 n \rceil - 1)$ matches. For $n = 8$: $7 + (3 - 1) = 9$, matching the count above.

What this means in practice

The puzzle is really a lesson in narrowing a search using structural information you already have, instead of restarting from scratch. In practice this maps onto ranking and elimination logic anywhere a bracket-like or knockout structure is used, for instance, narrowing which historical strategies to backtest further after an initial elimination pass, where you don't need to re-test every eliminated candidate, only the ones that lost to the eventual best.