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.