25 horses, 5 lanes. Find the fastest three.
The 25-horses puzzle, a Google classic: with no stopwatch and five lanes per race, how few races identify the three fastest horses? Six is not enough, eight is wasteful, and proving the right answer requires eliminating candidates you never raced against each other.
You have 25 horses and a track with 5 lanes, so each race pits exactly 5 horses against each other. You have no stopwatch: a race tells you the finishing order of its 5 entrants and nothing about absolute speed. Each horse always runs at its own constant speed, and no two horses are equally fast.
What is the minimum number of races needed to identify the fastest, second-fastest, and third-fastest horses, in order? Give a schedule that achieves it and an argument that fewer races cannot suffice.
Two boundaries frame the search. Five races are forced just to see every horse run once; a horse that never races could secretly be the fastest, so five is a hard floor. And a crude tournament plainly works: race five groups, then keep racing winners, then runners-up, spending ten or more races. The puzzle lives in the gap. The interesting work is not finding the top three, it is refusing to spend races confirming facts you can already deduce from finishing orders you have seen.
A concrete habit that helps: after each race, ask of every horse "how many distinct horses are now provably faster than this one?" The moment that count reaches three, the horse is dead to the podium and should never race again.
Stuck? Open hints one at a time
Each hint gives away one more layer. Stop the moment something clicks.
Hint 1 a nudge
Start with 5 races of 5, giving five internal orderings. Within each group, anyone who finished 4th or 5th has three group-mates provably faster. That alone eliminates 10 horses. What single race would let the group orderings eliminate across groups?
Hint 2 the key move
Race the five group winners against each other (race 6). Its winner is the fastest horse overall, outright. Now use transitivity aggressively: if a group's winner finished 4th or 5th in race 6, everyone in that group is out. Count who is still alive for 2nd and 3rd.
Hint 3 nearly the answer
Label race 6's finishers A, B, C, D, E and their groups likewise. Candidates for 2nd and 3rd: A's 2nd and 3rd, B's 1st and 2nd, and C's 1st. Everyone else already has three horses provably ahead. That is exactly five horses, one race left.
The solution
Reveal the full solution
Seven races. Five group races, one winners' race, one decider.
Races 1 to 5: split the horses into five groups and race each. Every 4th and 5th place finisher has three group-mates provably faster, so 10 horses are eliminated immediately.
Race 6: race the five group winners. Name them A, B, C, D, E in finishing order, and call their original groups A, B, C, D, E as well. A is the overall fastest, settled outright: A beat B through E directly, and by transitivity A beats everything in their groups.
Now prune candidates for 2nd and 3rd using transitivity alone:
- D, E, and their entire groups are out: each has at least A, B, C provably faster.
- Within group C, everyone below C is out (A, B, C are faster). Only C survives.
- Within group B, only B and B's runner-up survive (A and B outrank the rest).
- Within group A, only A's 2nd and 3rd place finishers remain candidates.
Race 7: exactly five candidates remain: A2, A3, B1, B2, C1. Race them; the top two finishers are the overall 2nd and 3rd fastest.
Why six races cannot work
After six races, at most 30 pairwise comparisons exist, direct plus transitive, and an adversary can always arrange results so that two surviving horses have no comparison path between them yet both remain podium candidates. Concretely: after races 1 to 6 above, A2 and B1 have never been compared, directly or through any chain, and either could be the true 2nd. Any schedule that avoids the winners' race does worse, leaving whole groups mutually incomparable. Since some pair of live podium candidates is always unresolved after six races, a seventh is forced.
What this puzzle is really testing
This is selection, not sorting. Fully ordering 25 horses five-at-a-time would cost far more than seven races; the schedule wins by refusing to learn anything irrelevant to the top three. That distinction, full sort versus partial selection, is exactly why quickselect finds the k-th element in linear time while a full sort pays the n log n toll, and why interviewers push back when you sort an array just to take the largest three. The elimination-by-transitivity bookkeeping is also a small taste of reasoning over partial orders, which returns in earnest with topological sort.
Follow-ups to expect
Top 4 instead of top 3 (answer: 8 races, and the candidate-counting method generalises). n squared horses with n lanes. And the sneaky variant with a stopwatch, where 5 races suffice because absolute times make every pair comparable. The last one is a reminder to re-check which constraint was doing the work.