Solution
The Two Strongest of Twenty
Show the problem again
Twenty players have distinct, fixed strengths (a stronger player always beats a weaker one, and the order is transitive). You do not know the strengths; the only operation is to pick two players and play one match, which reveals who is stronger. You may choose matches adaptively. You must determine who is the strongest and who is the second strongest. What is the smallest number of matches that is guaranteed to suffice, whatever the hidden strengths are?
Worked solution
The answer is n + ceil(log2 n) - 2 = 20 + 5 - 2 = 23. Upper bound: run a balanced knockout tournament (19 matches). The runner-up must have lost directly to the champion, who played at most 5 matches in a balanced bracket, so at most 5 players are candidates; a mini-knockout among them takes at most 4 more matches. Lower bound (Kislitsyn): an adversary can arrange that the eventual champion beats at least ceil(log2 n) opponents, and every non-champion except the runner-up must lose at least once, giving n - 1 + ceil(log2 n) - 1 matches. We checked the formula by exhaustive minimax for n = 2 to 6 and simulated the bracket strategy for n = 20.
Source: Kislitsyn (1964) and Schreier on selecting the two largest elements; Knuth, TAOCP vol. 3. Statement written for AxiomIQ.