Brain Teasers | Horse Race
Question: There are 25 horses, each of which runs at a constant speed that is different from the other horses. Since the track only has 5 lanes, each race can have at most 5 horses. If you need to find the 3 fastest horses, what is the minimum number of races needed to identify them?
Solution:
This problem is asked to test the basic analytical skills.
To find the 3 fastest horses, surely all horses need to be tested.
So the first step is to divide the horses into 5 groups (with horses 1–5, 6–10, 11–15, 16–20, 21–25 in each group).
After 5 races, we will have the order within each group, let’s assume the order follows the order of numbers (e.g., 6 is the fastest and 10 is the slowest in the 6–10 group). That means 1, 6, 11, 16 and 21 are the fastest within each group. Surely the last two horses within each group are eliminated.
We know that within each group, if the fastest horse ranks 5th or 4th among 25 horses, then all horses in that group cannot be in the top 3; if it ranks the 3rd, no other horse in that group can be in the top 3; if it ranks 2nd, then one other horse in that group may be in top 3; if it ranks the first, then two other horses in that group may be in top 3.
Let’s race horses 1, 6, 11, 16 and 21 assuming the order is 1, 6, 11, 16 and 21. Then we immediately know that horses 4–5, 8–10, 12–15, 16–20 and 21–25 are eliminated. Since 1 is the fastest among all the horses, 1 is in. We need to determine which two among horses 2, 3, 6, 7 and 11 are in the top 3, which only takes one extra race.
So all together we need 7 races (in 3 rounds) to identify the 3 fastest horses.
