Twenty-five horses, a track with five lanes, and no stopwatch: you only know who arrives before who within each race. The question is how many races do you need to be completely sure of who the three fastest are.
The twenty five horses
Riddle statement
You have 25 horses and a track with 5 lanes. Only 5 horses can compete in each race, and you do not have a stopwatch: you can only know the order of finish within each race.
What is the minimum number of races necessary to identify with certainty the three fastest horses?
Show solution
Solution
Answer: 7 races are needed.
Divide the 25 horses into 5 groups of 5 and run one race per group. After these 5 races you know the internal order of each group.
Let's call groups A, B, C, D, E, with their members already ordered:
and similarly for the other groups.
The sixth race pits the winners of each group against each other. Suppose the result is:
$A_1$ is the fastest of the twenty-five. Furthermore, it is possible to discard several horses without them running again:
no horse from D or E can be among the top three;
from C, only $C_1$ can aspire to the podium;
from B, only $B_1$ and $B_2$ can aspire;
from A, only $A_2$ and $A_3$ can aspire (since $A_1$ already occupies first place).
There are exactly five candidates left for second and third place:
A seventh race Among those five, the classification is resolved.
Six races are not enough: after the winners' race there are still five horses compatible with second and third place, and without facing them directly there is not enough information to order them.
The minimum is, therefore, 7 races.