Horses and Tracks

Question

I have seen this question before and I am intrigued that there might be various ways it can be solved. I do know of one way, but I am trying to find out if there is any other approach possible. The acceptable answer has to provide a methodology, preferably multiple, along with the answer to the question.

There are 25 horses and 5 tracks. Horses run at their original speed, regardless of how many races they run. What is the least number of races needed to determine the top 3 horses? There are no stopwatches or other equipment, and the only way to determine the order is ranking in a specific race.

Answer 1

Intuitive Solution:

When you first look at the problem, intuitively, it makes sense to first split the 25 horses into 5 groups and then run a race with each group - we will call these the 5 heats.

In the 6th race, you can run just the winners. Lets say that the results of this race are as follows:

1st place: A1
2nd place: B1
3rd place: C1

Without a doubt, you can say that A1 is the fastest horse. But how do you know if A2 (the horse that finished second in the heat with A1) is faster than B1 or not? In fact, you will have the following options for the 2nd and 3rd fastest horses overall:

1st overall: A1
2nd overall: A2 or B1
3rd overall: A3 or B2 or C1

So, a final (7th) consolation race is needed with A2, A3, B1, B2, and C1.

So, one solution would be that you need 7 races to decide the ordering of the top 3.

This all started with intuition, and while it may seem obvious that there isn't a better solution, perhaps there are equivalent ones.

Choices for heats

Perhaps a different way would be to run the first race to get 3 candidates, and then run the rest of the horses against one (or more) of these 3 to see how they fit in.

If you choose to run all three of the known horses in the subsequent races, it will take 10 more races to finish ordering all the horses since there are 20 horses who haven't yet run, and each race only has room for 2 more.

If you choose to run only 2 of the known horses in the next race, then it will take 7 more races before all the horses have run at least once (total of 8 races), and this is also worse than the best method so far. Even so, there may be additional races required to sort out the fastest 3.

If you choose a single known horse, then you have room for 4 new horses every race, so 5 more races (total of 6 so far). However, no matter which horse you choose to run again, in the worst case, you will add 2 horses to the list of possible "top 3" horses, so at the end, you will have 10 horses left who could qualify in the top 3. This would take 2 more races to sort out (total of 8 races). However, in the best case, (say you run A3 in the subsequent races and he wins every race) you would know the answer in only 6 races! Perhaps the average would be 7 races as well, but the worst case would be 8 or more.

Thus the optimal solution should include heats of 5 groups of 5.

Choices for 6th race

After the heats, you have 15 horses who qualified. You must be able to get the top three in some way from these 15. By running the winners in a single race, you will eliminate all the horses in the groups that finished 4th and 5th, as well as the two horses in the 3rd place group, and the third horse in the 2nd place group. This seems to minimize the remaining horses (5) and all fit into a single race for the consolation race, so there does not appear to be any obvious alternatives to the 6th race.

Choices for the 7th race

You will notice that the last race includes some known outcomes already. For example:

A2 is faster than A3
B1 is faster than B2
B1 is faster than C1

However, the unknowns are:

Is A2 faster than B1?
  If so, is A3 faster than B1?
    If so, then the order is A1, A2, A3
  otherwise
    The order is A1, A2, B1
otherwise Who is the fastest of A2, B2, and C1?
  If A2, the order is A1, B1, A2
  If B2, the order is A1, B1, B2
  If C1, the order is A1, B1, C1

So, we need a race that solves these questions. The only way to answer them all is to race these 5 horses.

Answer 2

I had so much fun with this puzzle that I made graphics to ask and then explain it.

First, let me start you with three clues:

1. I found it easier to think about this puzzle visually using a 5 × 5 grid
2. Your first race might contain the top three horses, so be careful
3. Since we want the top three horses, we can rule out any horse with three faster horses. The 4th and 5th finishers in a five-horse heat can't possibly be among the three we're looking for.

Each column of the above graphical answer is a "round" of races. There are five races (“heats”) in the first round 1 and one race each in the subsequent two rounds.

First round: Qualifying heats

Start with 5 races to get data on all horses.
We want the top three horses, so we can eliminate any horse with 3 faster horses.

Race 6 compares the winners of races 1–5. We sort races 1–5 by race 6’s outcome and rename them as A–E to denote their shuffling.

Second round: The fastest horse

Race 6 tells us our fastest horse overall. We can also eliminate its 4th and 5th fastest horses.

We can also use past knowledge to rank relative to the sixth race, so race C’s 2nd place is behind not only its 1st place but it is also behind race 6’s 1st and 2nd place horses. The arrows in each round’s mock-up demonstrate what we know so far. Round one eliminated 10 horses. Round two eliminates another nine.

Six horses remain (including our fastest).

Third round: The runners-up

As we already established, race 6 found us our fastest horse, so it doesn’t need to be raced again.

That leaves five horses for race 7. We know either race A’s 2nd or 6’s 2nd is our overall second-fastest horse since they're adjacent to our overall winner. Race 7 tells us not only our 2nd & 3rd fastest horses, it ranks 2nd–6th overall as well.