Solution
Ranking Eight Runners by Duels
Show the problem again
Eight runners have distinct, fixed speeds. A race pits two runners against each other and tells you only which is faster. You may choose each race based on earlier results. You want the complete ranking of all eight runners from fastest to slowest. What is the smallest number of races that is guaranteed to suffice, whatever the hidden order is?
Worked solution
The answer is 16. Lower bound: each race has two outcomes, so k races can distinguish at most 2^k orderings, and there are 8! = 40320 > 2^15 = 32768, so at least 16 races are needed. Upper bound: merge insertion (Ford and Johnson) first pairs the runners, recursively ranks the four pair winners, then inserts the remaining runners by binary search in the order that keeps every search over 1, 3, 7 slots. We ran the algorithm on all 40320 orderings: it always produced the correct ranking and the largest number of comparisons used was exactly 16.
Source: Merge-insertion sorting (Ford and Johnson, 1959), with the information-theoretic lower bound; see Knuth, TAOCP vol. 3. Statement written for AxiomIQ.