The Median of Five

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?

• combinations
• combinatorial games
• permutations
• pigeonhole

Source: Classic selection problem; see Knuth, TAOCP vol. 3 (selecting the median of five in six comparisons). Statement written for AxiomIQ.