Let’s say that you have 25 horses, and you want to pick the fastest 3 horses out of those 25. In each race, only 5 horses can run at the same time because there are only 5 tracks. What is the minimum number of races required to find the 3 fastest horses without using a stopwatch?
Solution:
Let’s say that we have 5 races of 5 horses each, so each row in the table above represents a race. So, “H1 H2 H3 H4 H5 ” represents a race, and so on. In each row, the fastest horses are listed in descending order, from the fastest (extreme left) to the slowest (extreme right). The fastest horses in each race are the ones on the left – so in the first race H1 was the fastest and H5 was the slowest and so on.
H1 H2 H3 H4 H5 H6 H7 H8 H9 H10 H11 H12 H13 H14 H15 H16 H17 H18 H19 H20 H21 H22 H23 H24 H25
After 5 races of 5 horses each, we have the 5 five fastest horses from each race (H1, H6, H11, H16, and H21). Remember we haven’t compared all the horses to each other since we can only run 5 horses in a race, so there is still a possibility that horses can be in any group. Since we have to find three horses, so we can eliminate the slowest 2 horses in each group since those horses are definitely not in the top 3.
Now, we can race those 5 horses against each other (H1, H6, H11, H16, and H21) and that would be the 6th race. Let’s say that the 3 fastest in that group are H1, H6, and H11. This means we can eliminate H16 and H21 row since horses from these rows 2 are definitely not in the top 3 i.e. we can eliminate H16, H17 H18, H21, H22 and H23.
Since H1 is the fastest horse in the group, now we have to find other two horses. If H6 and H11 are the 2nd and 3rd fastest in the group leaders, then we should be able to eliminate H8 since H6 raced against him and he was in 3rd place in that race, and H7 could only possibly be the 3rd fastest. We can also eliminate H12 and H13 since H11 was the 3rd fastest in the group leaders, and H12 and H13 were slower than H11. So, all together we have the following horses to determine the 2nd and 3rd fastest horses:
H2 H3 H6 H7 H11
Now we race those horses one more time – in the seventh (7th) race – and we can take out the top 2 horses and that would mean we have the 2nd and 3rd place horses! So it takes 7 races to find the top 3 horses.