Finding the Three Fastest of 25 Horses in Seven Races

Worked Solution

How to Think About It: With no stopwatch, races only give ordinal information, so this is a comparison-based selection problem where each "comparison" ranks 5 items at once. Think about what each race can rule out. A horse is out of the top 3 as soon as three horses are known (directly or by transitivity) to be faster than it.

Approach: Race in groups, race the winners, then use transitivity to shrink the candidate pool for places 2 and 3 to five horses, and race them.

Formal Solution:

*Step 1 -- Group races (races 1 to 5).* Split the 25 horses into 5 groups of 5 and race each group. Within each group we now know the full order. Label the groups so that their winners are $A_1, B_1, C_1, D_1, E_1$ and the horses of group $A$ in finishing order are $A_1, A_2, \ldots, A_5$, and similarly for the other groups.

*Step 2 -- Race of winners (race 6).* Race $A_1, B_1, C_1, D_1, E_1$. Relabel the groups so this race finishes in the order $A_1, B_1, C_1, D_1, E_1$. Then $A_1$ is the fastest horse of all: it beat every other group winner, and each group winner beat every horse in its group. This settles part (a): six races suffice for the fastest horse, and fewer cannot work because every horse must race at least once (5 races cover only 25 horses with no repeats, and you would still have 5 unrelated winners).

*Step 3 -- Eliminate by transitivity.* Which horses can still be second or third overall?

• Groups $D$ and $E$: their winners $D_1$ and $E_1$ already lost to $A_1, B_1, C_1$, so every horse in $D$ and $E$ has at least 3 faster horses. All 10 are out.
• Group $C$: $C_1$ lost to $A_1$ and $B_1$, so $C_1$ could still be third. But $C_2$ is behind $C_1, B_1, A_1$, so $C_2, \ldots, C_5$ are out.
• Group $B$: $B_1$ could be second, $B_2$ could be third (behind $B_1$ and $A_1$ only). $B_3$ is behind $B_2, B_1, A_1$, so $B_3, B_4, B_5$ are out.
• Group $A$: $A_2$ could be second, $A_3$ could be third. $A_4$ is behind $A_1, A_2, A_3$, so $A_4, A_5$ are out.

Exactly five candidates remain for places 2 and 3: $A_2, A_3, B_1, B_2, C_1$.

*Step 4 -- Final race (race 7).* Race those five horses. The first two finishers are the second- and third-fastest horses overall.

*Step 5 -- Why 6 races are not enough for the top 3.* Six races provide only $30$ slots for $25$ horses, so at most $5$ slots are repeat appearances and at least $20$ horses race exactly once. To certify the top three, each of the other $22$ horses must be known, directly or by transitivity, to be slower than three horses, and the top three must be mutually ordered. The interview-level argument: the only way to see every horse in five races is five disjoint groups, and a sixth race can compare at most five horses across groups; if it races the five group winners, the runner-up of the winning group ($A_2$) has never been compared with the runner-up group's winner ($B_1$), so second place is undetermined; if it does not race all five winners, some group winner has never been compared with any horse outside its group and could still be the fastest. A rigorous version considers an adversary who answers every race consistently with all previous results, always ranking the horses in a race by how many horses are already known to be faster than them (fewest first, ties to horses that raced earlier). An exhaustive search over every adaptive 6-race schedule against this adversary (about $500{,}000$ positions after removing symmetries) finds no schedule that pins down the top three, so no strategy can guarantee success in 6 races and 7 is the minimum.

Answer: (a) 6 races. (b) 7 races: 5 group races, 1 race of the group winners (its winner is fastest overall), then 1 race among $A_2, A_3, B_1, B_2, C_1$ whose top two are the second- and third-fastest horses.