Finding the Top Three Horses in Minimum Races

Worked Solution

How to Think About It: This is a classic comparison-based selection problem. You cannot time horses, only compare within a race. The naive approach -- race every pair -- takes far too many races. The key insight is to use a tournament structure: first find the fastest horse, then carefully narrow down the candidates for 2nd and 3rd place using information you have already gathered.

Quick Estimate: You have 25 horses and can compare 5 at a time. Just to see every horse at least once, you need $\lceil 25/5 \rceil = 5$ races. That is clearly not enough to identify the top 3 (you only know the winner of each group). You will need some additional races. Since the answer should be small, guess 6 or 7.

Approach: Tournament elimination followed by a carefully chosen final race.

Formal Solution:

Races 1-5: Divide the 25 horses into 5 groups of 5. Race each group. This takes 5 races.

Label the results: let the horses in group $g$ be $g_1, g_2, g_3, g_4, g_5$ in order of finishing (so $g_1$ is the fastest in group $g$). We now know the ordering within each group.

Race 6: Race the 5 group winners: $A_1, B_1, C_1, D_1, E_1$.

Without loss of generality, suppose the result is $A_1 > B_1 > C_1 > D_1 > E_1$.

Now we can deduce:

• $A_1$ is the overall fastest. No horse beat $A_1$ in any race.

• Candidates for 2nd and 3rd overall must be horses that could plausibly be faster than all but at most 2 others. Let's carefully eliminate:

• $D_1$ finished 4th among group winners, so at least 3 horses are faster ($A_1, B_1, C_1$). So $D_1$ is at best 4th overall. Eliminated, along with all of group $D$ (since $D_2, D_3, \ldots$ are slower than $D_1$).
• $E_1$ finished 5th among group winners. Eliminated, along with all of group $E$.
• $C_1$ finished 3rd among group winners, so $C_1$ could be 3rd overall at best. But $C_2$ and below lost to $C_1$, who is at best 3rd, so $C_2, C_3, \ldots$ are eliminated.
• $B_1$ finished 2nd among group winners, so $B_1$ could be 2nd overall. $B_2$ could be 3rd overall (faster than everyone except $A_1$ and $B_1$). But $B_3$ and below lost to both $B_1$ and $B_2$, plus $A_1$ is faster, so $B_3$ is at best 4th. Eliminated.
• $A_2$ could be 2nd overall (only lost to $A_1$). $A_3$ could be 3rd overall (only lost to $A_1$ and $A_2$). But $A_4$ and below are eliminated ($A_4$ lost to $A_1, A_2, A_3$ -- at best 4th).

The surviving candidates for 2nd and 3rd place are:

$\{A_2, A_3, B_1, B_2, C_1\}$

That is exactly 5 horses.

Race 7: Race $A_2, A_3, B_1, B_2, C_1$. The top 2 finishers in this race are the 2nd and 3rd fastest overall.

Total races: $5 + 1 + 1 = 7$.

Why 6 races are not enough:

After 5 initial races, you know the ordering within each group but nothing about cross-group comparisons. Race 6 (the winners' race) gives you the overall fastest and an ordering of winners, but the 5 candidates for 2nd/3rd could be in any order relative to each other. No single prior race resolved their relative speeds, so you need at least one more race to sort them out. A formal information-theoretic argument confirms that 6 races are insufficient to guarantee identification of the top 3.

Answer: The minimum number of races is $\boxed{7}$.