The 25 Horses Problem

Photo Credit: WeGraphics

The 25 Horses Problem

One interesting question comes to me from the one issue of The Bloomberg Businessweek.

The problem is just as follows:

The 25 horses problem

You have 25 horses and can race them in heats of 5. You know the order the horses finished in, but not their times. How many heats are necessary to find the fastest? First and second? First, second, and third?

The solution given by the magazine is six, seven, and seven. Knowing the solution makes the problem a lot simpler. Let us take a look at how to achieve this.

The first is straightforward. We pick up 5 horses and find the fastest one. Repeat that process 4 more times and find 5 group winners. Then get this 5 around and race one more time. We have totally 5+1=6 heats consumed.

The second is a little bit tricky. We need to group the horses into 5 5-horse groups. Run five heats and find the first two within each group (F means faster and S means slow). Next step is critical. Run the heat again for the five fastest horses we just picked. Ha, now we can rule out many options (marked with dark grey). Notice we only have four left (still in white). Run it again and done.

1-1

The third is quite like the second. Group the horses into 5 5-horse groups. Run five heats and find the first three within each group (again F means faster, M means medium, and S means slow). Run the heat again for the five fastest horses we just picked. Again, we can rule out many options. Notice this time we have six left. But wait. The fastest in the last run must be the fastest for all so we do not need to care about it (marked with red). You may need some thought on why we rule out so many.

1-1

This problem involves some general concerns.

The limitation of this problem is: we have to gain as much information as possible every measurement. Take the second problem as an example. Since we need to find out the first and second fastest horses, during every measurement we have to keep the two fastest horses and rule out the slowest three (they will never be the fastest two). However, following this simple thought, every measurement rules out three and totally we need to rule out 23 horses, then we need 23/3 > 7 times of measurements. You might notice that in our strategy the ruling out process speeds up in step 2 in which we actually rule out groups!

The trivial lower bound of this problem is 25/5 since at least every horse has to be in the measurement once, this bound is never reachable because in this case each measurement does not relate to the other.