Twenty-five horses, five lanes
You have 25 horses, each with its own constant speed, all different. The track has 5 lanes, so at most 5 horses can run in a race, and a race tells you only the order in which they finish, not their times.
What is the smallest number of races that always identifies the three fastest horses, in order?
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
Every horse has to race at least once. Start with five races of five horses each.
Race the five winners against each other. Which horses can still be among the three fastest?
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. Five heats and a race of the heat winners pin down the fastest horse and leave only five candidates for second and third place. A seventh race settles them.
Races 1 to 5. Split the horses into five groups and race each group. Within a group, call the horses 1, 2, 3, 4, 5 in finishing order.
Race 6. Race the five group winners. Name the groups A, B, C, D, E by the finishing order of their winners in this race. Then A1 is the fastest horse overall.
Who is left for second and third?
- D1 and E1 are slower than A1, B1 and C1, so they are not in the top three, and neither is anyone in groups D and E.
- In group C, C2 is slower than C1, B1 and A1, so only C1 remains.
- In group B, B3 is slower than B2, B1 and A1, so B1 and B2 remain.
- In group A, A2 and A3 remain.
That leaves five candidates: A2, A3, B1, B2, C1.
Race 7. Race those five. The first two finishers are the second and third fastest horses overall. So 7 races are enough.
Why 6 are not enough. Call a horse unbeaten if it has never finished behind another horse. At the start all 25 are unbeaten, and to know the fastest horse only one may be left. A race can beat at most 4 unbeaten horses, so at least races are needed just to find the fastest, and 6 is possible only if every race contains five unbeaten horses.
Then a horse that loses never runs again. If the fastest horse won two races, the two runners-up have each lost only to it and never met, so second place is unknown. Following this kind of argument through the remaining cases shows that, whatever six races are run, some finishing orders leave two candidates for second or third place that never met. So the scheme above, with 7 races, is the best possible.