Puzzle 17: Top 3 among 25 horses

Puzzle 17: You have 25 horses. When they race, each horse runs at a different, constant pace. A horse will always run at the same pace no matter how many times it races.

You want to figure out which are your 3 fastest horses. You are allowed to race at most 5 horses against each other at a time. You don't have a stopwatch so all you can learn from each race is which order the horses finish in.

What is the least number of races you can conduct to figure out which 3 horses are fastest?

Show Solution

Solution: You need to conduct 7 races.
Explanation:

First, separate the horses into 5 groups of 5 horses each, and race the horses in each of these groups. Let's call these groups A, B, C, D and E, and within each group let's label them in the order they finished. So for example, in group A, A1 finished 1st, A2 finished 2nd, A3 finished 3rd, and so on.

We can rule out the bottom two finishers in each race (A4 and A5, B4 and B5, C4 and C5, D4 and D5, and E4 and E5), since we know of at least 3 horses that are faster than them (specifically, the horses that beat them in their respective races).

This table shows our remaining horses:

A1	B1	C1	D1	E1
A2	B2	C2	D2	E2
A3	B3	C3	D3	E3

For our 6th race, let's race the top finishers in each group: A1, B1, C1, D1 and E1. Let's assume that the order of finishers is: A1, B1, C1, D1, E1 (so A1 finished first, E1 finished last).

We now know that horse D1 cannot be in the top 3, because it is slower than C1, B1 and A1 (it lost to them in the 6th race). Thus, D2 and D3 can also not be in the to 3 (since they are slower than D1).

Similarly, E1, E2 and E3 cannot be in the top 3 because they are all slower than D1 (which we already know isn't in the top 3).

Let's look at our updated table, having removed these horses that can't be in the top 3:

A1	B1	C1
A2	B2	C2
A3	B3	C3

We can actually rule out a few more horses. C2 and C3 cannot be in the top 3 because they are both slower than C1 (and thus are also slower than B1 and A1). And B3 also can't be in the top 3 because it is slower than B2 and B1 (and thus is also slower than A1). So let's further update our table:

A1	B1	C1
A2	B2
A3

We actually already know that A1 is our fastest horse (since it directly or indirectly beat all the remaining horses). So now we just need to find the other two fastest horses out of A2, A3, B1, B2 and C1. So for our 7th race, we simply race these 5 horses, and the top two finishers, plus A1, are our 3 fastest horses.