There are 25 horses and a track where at most 5 can run at once. There is no stopwatch: a race shows only who finished first, who second, and so on. Each horse always runs at the same speed, and all speeds are different. What is the smallest number of races that guarantees you find the three fastest horses and know which is first, second and third?
Six looks like enough: five races of five horses, then a race of the winners. But the winners' race reliably finds only the fastest horse. The second fastest may be the one that lost to it back in their own heat. So you need a seventh race, for the five horses that can still be second or third.
A classic interview puzzle for programmers: William Poundstone presents it as a Google interview question (2012). It does not test formulas. It tests whether you notice exactly what each race has already proved, and avoid spending a race on what you already know.
25 horses, numbered 1 to 25. They all look alike, so the only way to learn who is faster is to race them.
The track has 5 lanes, so at most 5 horses run in one race. Fewer is allowed too.
There is no stopwatch. A race tells you only the finishing order: who is first, who is second, and so on. You cannot compare times across races.
Each horse always runs at the same speed, never tires and never holds back. All 25 speeds are different, so there are no ties.
What is the smallest number of races that guarantees you find the three fastest horses and their order?
"Six: five races of five, then a race of the winners"
More careful people sense a trap and say 10 or 11. In fact exactly 7 are needed. The sixth race finds the fastest horse, but its finishing order gets the whole top 3 right only with probability 25/46, about 54%. And six races are not enough with any strategy.
25 horses, 5 lanes, finishing order only. Lock in the smallest number of races that, in your view, guarantees the result.
A breakdown of your answer will appear here.
Hard to decide? Open the hints one at a time: the easy one first, then stronger ones.
No stopwatch, so times can't be compared across races. Before each race, ask what you already know for sure and who can no longer make the top 3.
Start with five heats of five and a race of the winners. Then for each horse count how many horses are surely faster: three or more, and it is out.
After the winners' race you know the fastest. Who can still be second or third? Nobody from the heats whose winners came fourth and fifth.
Pick up to 5 horses and press "Start". The speeds are not fixed in advance: an evil stable makes them up after seeing your choice. It never contradicts earlier results, but every time it picks the finishing order that keeps as many horses in play as possible. The game ends when first, second and third follow from the results with no doubt left.
Each time the horses get random speeds. First come five races of five and a winners' race. The naive answer takes the top 3 of the winners' race. The full strategy runs one more race for the five contenders. We compare which one names the true top 3, and split the outcomes of the seventh race into five possible scenarios.
After the winners' race we label the heats with letters: A is the heat of the fastest winner, B the next one, and so on; the digit is the place within the heat. The bars show who finished first and second in the seventh race, which is who is really second and third.
The key is to count, after every race, how many horses are surely faster than each horse. A horse with three surely faster horses can no longer make the top 3, and there is no point in racing it again.
Horse C2 is slower than C1, C1 is slower than B1, and B1 is slower than A1. So three horses are surely faster than C2, and it cannot make the top 3. In the same way the whole of heats D and E drop out, as do A4, A5, B3, B4, B5 and C2–C5. Left are A1, A2, A3, B1, B2 and C1. A1 is the fastest: it won the winners' race. So the seventh race is A2, A3, B1, B2 and C1, exactly five horses, as many as there are lanes.
Only A2 or B1 can be second fastest: every other contender has at least two surely faster horses. Both run in the seventh race, so its winner is second overall. Third is whoever finishes second in that race: every contender behind it is slower, and every horse outside the race, except A1, has three surely faster horses.
Call a horse unbeaten if no horse has finished ahead of it yet. At first there are 25 unbeaten horses, and at the end exactly one must remain. Let every race be won by an unbeaten horse whenever one is running, and among those by the one that has raced the most. That never contradicts any result, and then a race takes the status away from at most 4 horses. 24 / 4 = 6, so just finding the fastest takes 6 races. And if there are exactly 6, each of them has five unbeaten horses.
Then the winner of the fifth race is still unbeaten and has to run in the sixth, so the champion has raced at least twice. The runners-up of those two races lost only to the champion and never ran again: nobody knows which of them is faster. So every strategy needs a seventh race.
The winners' race tells the truth about the top 3 only when the three fastest horses ended up in three different heats. The second fastest avoids the heat of the fastest with chance 20/24: 4 of the 24 remaining places are in it. The third avoids both of those heats with chance 15/23. Together that is 25/46 ≈ 54.3%, so in almost half the cases six races give the wrong top 3.
In the poisoned wine puzzle counting outcomes gives the bound, and it is tight. Here it says almost nothing: two races give 120² = 14,400 outcomes, more than the 13,800 possible top 3s. But a race cannot ask about anything you like. It compares only the horses that ran together, and each of the 25 horses needs a lane in at least one race. The limit is in the lanes, not in the bits.
Race results form a directed graph with no cycles: an arrow goes from the faster horse to the slower one. It defines a partial order: for some pairs of horses we know which is faster, for others we do not. The true speeds are one of the linear orders consistent with all the arrows.
A horse's ancestors are all horses with a path of arrows leading to it, that is, all surely faster horses. A horse can finish k-th in some consistent order if and only if it has at most k − 1 ancestors (and not too many descendants). Just place all its ancestors first, then the horse itself. So only horses with 0, 1 or 2 ancestors can still make the top 3.
After the sixth race, the horse that finished j-th in the heat with letter number i has exactly (i − 1) + (j − 1) ancestors. Click a circle to see them. A graph without a single redundant edge, like this one, is called a Hasse diagram.
Horse Xij finished j-th in the heat whose winner placed i-th in the winners' race. Surely faster than it: j − 1 heat-mates and i − 1 winners of better heats.
Only a horse with at most two ancestors can make the top 3.
Minus A1, already known to be the fastest. The five contenders exactly fill the lanes, so the total is:
The lower bound: each race takes the unbeaten status from at most 4 horses, and 24 must lose it.
The chance that the winners' top 3 is right: the three fastest horses are in three different heats.
The strategy not only meets the bound, it also wastes no lane: each of the seven races has five horses, and each of them could still have been in the top 3.
The horse puzzle belongs to the theory of selection: how to find the best by comparing items in small groups. In mathematics it leads to optimal tournaments, in logic to Lewis Carroll's old complaint about tennis, and in practice to how databases find the top k rows.
Mathematics
For 25 horses the fastest takes 6 races, the two fastest take 7, and the top three also take 7. The same argument works for n lanes and n² horses. Each race takes the unbeaten status from at most n − 1 horses, and n² − 1 must lose it, so first place alone needs (n² − 1)/(n − 1) = n + 1 races, and n heats plus a winners' race achieve it.
The argument about the champion's two runners-up gives n + 2 for second place, and the contenders' race A2, A3, B1, B2, C1 fits on the track when n ≥ 5. So the top three also take n + 2. With 4 lanes and 16 horses there are five contenders and four lanes, and it is no longer that simple. Finding the fourth or fifth horse is harder too: after the winners' race there are k(k + 1)/2 − 1 contenders, which is 9 for k = 4.
With two lanes a race becomes a plain comparison. A knockout tournament finds the champion in n − 1 matches: each match knocks out one player. Only someone beaten by the champion can be second, because everyone else lost to somebody who is not the best. The champion played at most ⌈log₂ n⌉ matches, so another ⌈log₂ n⌉ − 1 comparisons among its opponents finish the job.
Józef Schreier described this method in 1932 and believed it optimal, but his proof had gaps. A complete proof that fewer than n + ⌈log₂ n⌉ − 2 comparisons cannot work came from S. S. Kislitsyn in 1964. For 25 horses on two lanes that is 28 races.
Logic
The numbers in the bracket are the players' true strength: 1 is the strongest, and the stronger player always wins. Player 1 always becomes champion. But silver goes to the strongest player in the other half of the bracket. The true number 2 gets it only if the draw put them in the other half, a chance of 8/15 ≈ 53% for 16 players and 16/31 ≈ 52% for 32. Carroll computed this 16/31 himself in an 1882 letter to the St James's Gazette.
In 1883 the mathematician Charles Dodgson, known as Lewis Carroll, published a pamphlet, "Lawn Tennis Tournaments", whose subtitle promised a proof of "the fallacy of the present method" of awarding prizes. His complaint is the same as in the horse puzzle: a knockout does not prove who is second. A second round for those who lost to the champion is exactly our seventh race.
Practice
The naive way finds the second largest number in two passes: first the maximum in n − 1 comparisons, then the maximum of the rest in n − 2 more. A tournament saves almost half, because the second pass runs only over the champion's ⌈log₂ n⌉ opponents. For a million numbers that is 1,000,018 comparisons instead of 1,999,997. Check it with the button: the page counts every comparison.
The same idea lives in sport: in Olympic wrestling the repechage, which decides the bronze medals, is for those who lost to the finalists, since only they could be stronger than the rest. In programming the tournament tree turns into a heap, and PostgreSQL runs "ORDER BY … LIMIT k" without a full sort: the EXPLAIN ANALYZE plan shows "Sort Method: top-N heapsort".
Charles Dodgson, an Oxford mathematician better known as the author of "Alice's Adventures in Wonderland", published a pamphlet, "Lawn Tennis Tournaments: The True Method of Assigning Prizes with a Proof of the Fallacy of the Present Method". He argued that a knockout hands out second and third prizes unfairly.
The Polish mathematician Józef Schreier, in a paper in "Mathesis Polska", showed how to find the best and second-best player in n + ⌈log₂ n⌉ − 2 comparisons and claimed that no method does better. His proof turned out to be incomplete.
32 years later S. S. Kislitsyn, in the Siberian Mathematical Journal, finally proved that n + ⌈log₂ n⌉ − 2 comparisons really are necessary. It was one of the first exact results on the cost of selection, as opposed to full sorting.
In volume 3 of "The Art of Computer Programming" (1973), Donald Knuth devoted section 5.3.3 to minimum-comparison selection. He begins the history of the question with Dodgson's 1883 essay on lawn tennis tournaments and goes on to the results of Schreier and Kislitsyn.
In 1973 Blum, Floyd, Pratt, Rivest and Tarjan showed how to find the median in linear time even in the worst case. The algorithm splits the numbers into groups of five, like horses into heats, and takes the median of the medians. Four of the five authors later received the Turing Award.
That is how many ordered podiums 25 horses allow, while one race has 5! = 120 possible results. Bare counting promises 2 races, since 120² = 14,400. The real answer is more than three times larger, because a race compares only the horses that ran together.
Share your own explanation, an objection or a variant of the puzzle. You need a GitHub account to comment.
I keep adding new puzzles, new ways to explain them and write-ups of the discussions they start. Leave your email and I'll write when something new is out. No spam, one-click unsubscribe.
The sign-up form will appear here soon.