25 horses, 5 tracks, find the top 3

Question

You have 25 horses and want to find the three fastest. You have a race track that can run only 5 horses at a time, and you have no stopwatch, a race tells you only the relative finishing order of those 5 horses. Assume each horse runs at a fixed speed with no ties. What is the minimum number of races needed to identify the top 3 horses (in order), and how?

Accepted Answer

The answer is 7 races. Races 1–5. Divide the 25 horses into 5 groups of 5 and race each group. Label the groups A,B,C,D,E and their finishers by rank, e.g. A1,A2,A3,A4,A5 from fastest to slowest within group A. That's 5 races. Race 6. Race the five group winners A1,B1,C1,D1,E1. Suppose the finishing order is A1 B1 C1 D1 E1. This makes A1 the fastest horse overall. It also lets us eliminate many horses: - D1, E1 and everyone behind them (groups D and E entirely) cannot be top 3, since D1 already has three horses proven faster (A1,B1,C1). - C2, C3, \dots are out: C1 is behind A1,B1, so anything…

25 horses, 5 tracks, find the top 3

Your answer

More Brainteasers questions