Brainteasers · Weighing and search · Medium
Nine horses, three lanes
Nine horses each run at their own fixed speed, all different, so a faster horse always beats a slower one. You have no clock. The track takes at most three horses in a race, and a race tells you the full finishing order of the horses in it and nothing else. What is the smallest number of races that is certain to identify both the fastest horse and the second fastest, knowing which is which, however the races turn out?
Answer and solution
Answer
5
Solution
The second fastest horse is one that has been beaten only by the champion, and the champion has beaten a direct runner-up in two different races.
Run three heats of three, then race the three winners: the winner of that race is the fastest. The second fastest was beaten only by the champion, so it is either second in the winners' race or second in the champion's heat. Race those two: 5 races. Four cannot do it: four races find the fastest only if every race is among unbeaten horses, and the results can always make the champion a horse that won two of them, leaving two runners-up that have never met. The answer is 5.