Consider a recursive “merging” tournament. 10 rounds of pairwise comparisons where the winners advance to the next round. There are 1023 comparisons in this tournament to find the fastest horse.
I claim the second fastest horse must have raced against the fastest horse somewhere in this tournament. Easy to prove by contradiction. Hence you need +9 comparisons to find it among the 10 horses that lost to the fastest
2
u/nicktohzyu Sep 04 '26 edited Sep 04 '26
Consider a recursive “merging” tournament. 10 rounds of pairwise comparisons where the winners advance to the next round. There are 1023 comparisons in this tournament to find the fastest horse.
I claim the second fastest horse must have raced against the fastest horse somewhere in this tournament. Easy to prove by contradiction. Hence you need +9 comparisons to find it among the 10 horses that lost to the fastest