Don’t Hold Your Horses: Race ‘em!

Comments by Steve Miller and Rebecca Silva

Problem Stated below:

“You have 25 horses and want to know which are the three fastest. Whenever you race horses, the order of finish accurately reflects the relative speeds of the horses but you can only race five at a time. What’s the minimum number of races required to determine the three fastest, and how do you do it?”

 We give a chain of hints below, then the solution,  then some interesting problems to ponder.

First hint:

            After reading this problem, you may want to jump right into seeing how many races are needed to find the three fastest horses. The hardest thing about finding the minimum number is being sure the answer cannot get any smaller. Instead of looking for a minimum right off the bat, the best way to approach this problem is first, understanding it well. After understanding the problem well, you should start playing around with number of races. Without thinking about a minimum you first just need to find a number that you can be sure will determine the top three horses. It’s okay if that answer is far from the truth – try and get some result, any result, at first and then work on improving it. Our goal of this step is simply to get a number of races we can work with. For example, can you show that you can do it in at most 25 races? What about 24 or 23? Try doing things very crudely, and then later try to improve.

 

Second hint: 

It is essential to note that the only way to know the speed of the horses is from their relative speeds with other horses. There is no timer so knowing how one horse does in a race does not tell us how fast another horse is in a different race. For example, the fourth fastest horse in one group of five could be the fastest horse in another group of five. Lastly, remember only five horses can be in one race and there are 25 total horses.

Is there a way to show 21 races suffice? Think about how we can directly compare every horse with every other horse.

Third Hint:

What if we race the first five, and then throw away the two slowest and replace those with the next two horses. We then throw away the two slowest of that race and replace with the next two horses from our list of 25. If we continue along these lines what would we get? This of course seems very wasteful. Maybe we should have different groups of 5 horses race and then combine them, rather than slowly changing just the last two horses.

 

Fourth Hint:

Of course, every horse must race at least once, but every horse does not have to race every other horse, nor do all horses have to race the same number of times. We can use the results of previous races to collect horses well to save on future races.

 

 

Fifth Hint:

Try seeing what happens after racing all 25 horses in five groups with no horse in two groups. After five races, we are left with five independently ordered groups of horses. Each group is ordered from one to five, with one being the fastest in the group, and five being the slowest in the group.

With five independent groups, we can come up with three possible scenarios for the overall three fastest horses:

1. the top three could be the first three in one group,
2. the first two in one group and the first in another, or
3. the first from three different groups.

 

Do these scenarios automatically eliminate horses from each of the first five groups? You should be able to eliminate 10 horses from our initial 25 horses. Keep in mind that we are only looking for the three fastest horses overall.

 

10 Races:

No matter what we do next after our initial five races, there is no use racing the fourth and five place finishers in each group. It is impossible for a fourth place finisher to be one of the three fastest horses since that horse did not even get top three in their own heat. This eliminates 10 horses (the bottom two from each group) and we are left with 15 horses. Before reading on, try to come up with different ways you can race the top three horses in five groups.

• Race 6: Race the top three of group 1 with the top two of group 2.
• Race 7: Race the top three of group 2 with the top two of group 3.
• Race 8: Race the top three of group 3 with the top two of group 4.
• Race 9: Race the top three of group 4 with the top two of group 5.
• Race 10: Race the top three of group 5 with the top two of group 1.

 

After these five additional races we will have raced all fifteen horses. Specifically, we will have raced the top two of each group twice and the third horses from each group once. The results from these races will give us sufficient information to figure out the three overall fastest horses because we have compared each group to the other groups.

 

Sixth Hint:

We are making important steps so that we can eventually find the minimum number of races. How do you know when to stop? You will know you found a minimum when you can prove you need at least that number of races to determine the three fastest horses.

Before looking ahead, think about the ways you can arrange 15 horses. Consider why some groups of horses might be more efficient to race than others.

 

9 Races:

We will start again with having five initial races to race all 25 horses. We know from reasoning we used to find 10 races, that we can eliminate the bottom two horses from each group.  We are left with 15 horses.

• Race 6: Race the first place finishers in each of the five heats.
• Race 7: Race the second place finishers in each of the five heats.
• Race 8: Race the third place finishers in each of the five heats.

 

For the purposes of making this problem simpler to understand, we will denote the top three in group 1 as and , and the top three in group 2 as and , and so on. After these races we can eliminate the fourth and fifth place finishers from race 6, race 7 and race 8. For example if finish fourth and fifth in race 6, we can eliminate them because we know that they are not one of the three fastest.

We are now left with nine horses. Think about which other horses should be eliminated before adding on another race.

We can eliminate the second and third place finishers from race 8. We can do this because we know that those two third place finishers in two groups are not as fast as the third horse in another group so it is impossible that they are in the overall top three. We can use similar logic to eliminate the third horse in race 7. This is because the third horse who was second in their initial group is still slower than two other second place finishers from the initial heats and at least two first place finishers from the initial heats. For example if came third after  and , we can be sure that at least  are faster than .

The horses left are now the top three from race 6, the top two from race 7, and the top horse from race 8. This leaves six horses. Which horse of the six do we already have enough information about? We know the first place finisher from race 6 is the fastest horse overall so we can take that horse out of the next race. Therefore, our last race is:

• Race 9: the second and third horses from race 6, the top two horses from race 7, and the top horse from race 8.

After race 9 we will know the second and third fastest horses, so we will be done.

 

Solution:

Now we will try to use logical deduction starting from the first five races to find the minimum number of races needed. We will continue to denote the top three in group 1 as and , and the top three in group 2 as and , and so on. We can eliminate the fourth and fifth horses from each heat because we know it is impossible for them to be in the overall top three when they were not even top three in their own heat. The figure below might make it easier to picture why specific eliminations make sense. For the purposes of the following demonstration we assume the order in each group is a, b, c, d, and e, with a being the fastest and e being the slowest.

Next, we ask ourselves which horses must be in another race. We will need to race the first horse from each heat again ( This race is necessary because it will help us compare the five initial groups. Instead of thinking about who the next race should include we should see if we can deduce anything from the results of this race.

It is important to find which horses we can eliminate at each step. This race will give us the top three groups. For example, let us say that  finish top three. Since  do not make the top three, we know that there is no way  are in the top three because they are slower than respectively. Furthermore, we can eliminate  because  finishes third in the race so there is no way two slower horses could make the top three. Lastly, we can deduce one more thing from this race. We can eliminate  because even if  was right behind  the top three horses would be These eliminations are shown in red below.

Reviewing from the beginning, after racing all 25 horses we could eliminate 10 horses and were left with 15 horses. Then we raced the first horse in each of the five heats. From this race we were able to eliminate 9 horses. We are now left with 6 horses. Not all 6 horses will fit in a race but since we know the overall fastest horse from being the winner of the race with the first horses from each heat, we do not need to put that horse in another race. Therefore our next race will include  (in case the top three are all in the same heat),  and . The top two from this race will determine the second and third fastest horses. We then know the top three horses because we already know the overall fastest horse.

Our total number of races is 7. This is the minimum because after racing all 25 horses we first have to compare the initial 5 groups, and then compare the top horses in the best groups.

 

Thoughts:

If we compare the solution with 7 total races to the solution with 9 total races we see similar deductions. The difference between the two solutions was that in our second solution we made these deductions earlier. We did not need to race the second place finishers in each of the five heats and the third place finishers in each of the five heats.

This problem can be overwhelming because there are so many possibilities for how the horses can compare. The solution comes easiest when you set a weak bound and work from there. We learned that to find the minimum we simply have to start with what we know is necessary and use logical deductions at each step to eliminate horses.

 

ADVANCED PROBLEM:

In the analysis below we definitely show 7 races work, but could 6 work?  We could try to make the argument tighter above and show that 6 fail, or we could do a brute force analysis. Now, brute force is probably going to be too much to be manageable on an available computer, but let’s see.

If there are 25 horses, there are (25 choose 5) = 25! / 5!20! = 25*24*23*22*21/5*4*3*2*1 = 53,130 ways to choose 5 from 25.  Thus the number of ways to choose six distinct groups of 5 horses to race is ((25 choose 5) choose 6) = (53130 choose 6), which is about 3.12 * 10^{25}. There is no way we can compute anything that large — at best we can get up to maybe 10^{14}.

If we want to show, by brute force,  that it is impossible to do in 6 races we need to do a lot better than going through all 53130. Hint: every time we race 5 horses, we throw away the two slowest. Thus there are 25 candidates for the first race (and we choose 5), then 23 for the next and we choose 5, …. This will help, but will it help enough? Can you find a way to brute force and eliminate 6 races?