Ranking Eight Runners by Duels
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?
Related problems & prerequisites
Worth solving first
- Five Weights on Both Pans 7.0/10
- Twenty-Five Horses 6.0/10
- Three Switches, One Bulb 5.0/10
Source: Merge-insertion sorting (Ford and Johnson, 1959), with the information-theoretic lower bound; see Knuth, TAOCP vol. 3. Statement written for AxiomIQ.