mathematics - Horses and Tracks

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

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.

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.

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.

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.