Solution
The Median of Five
Show the problem again
Five runners have distinct, fixed speeds. Each race pits two runners against each other and shows only which is faster. You may choose races adaptively. You want to identify the median runner, the one who is exactly third fastest, without necessarily knowing the complete order of the others. What is the minimum number of races that is guaranteed to suffice?
Worked solution
The answer is 6. Strategy: race a vs b and c vs d, then race the two winners; call the overall winner of that third race W. W beats three others, so W cannot be the median and is discarded. Say a beat b, c beat d, and a beat c, so W = a. Since a is above the median, the median is the second fastest of b, c, d, e, where c beats d. Race b against e (4th race) and call the winner x and the loser y. Race x against c (5th race). If x wins, the answer is the faster of c and y; if c wins, it is the faster of d and x. That last race is the 6th. We checked this strategy on all 120 orderings. For the lower bound, we ran an exhaustive minimax search over all sets of orderings consistent with the results so far: no strategy always finds the median in 5 races.
Source: Classic selection problem; see Knuth, TAOCP vol. 3 (selecting the median of five in six comparisons). Statement written for AxiomIQ.