Expanding on Tony K's comment, here's an (extreme) example of why it's impossible.
Let's say that we have three very strange horses:
- Horse A runs the race in $1$ second with probability $1/2$, and in $9$ seconds with probability $1/2$.
- Horse B runs the race in $3$ seconds with probability $1/2$, and in $7$ seconds with probability $1/2$.
- Horse C always runs the race in $5$ seconds.
Then it's not hard to check that, in head-to-head races, $P(A \text{ beats } B) = P(A \text{ beats } C) = P(B \text{ beats } C) = 1/2$.
In a three-way race, A will win whenever it runs fast, so $P(A \text{ wins})=1/2$. If A doesn't run fast, B will win if it runs fast, and C will win if B runs slowly. So $P(B \text{ wins})=P(C \text{ wins})=1/4$.
On the other hand, let's say we have three more normal horses; in fact, horses D, E, and F are so ordinary that they're identical to each other in every way. Then it must be true that $P(D \text{ beats } E) = P(D \text{ beats } F) = P(E \text{ beats } F) = 1/2$ again. But in this case, each horse must have a $1/3$ probability of winning the entire race.
That is, we've found two sets of three horses such that:
- The head-to-head probabilities are identical between them.
- The probabilities of winning a 3-way race are different.
So there can't possibly be any way of calculating the 3-way probability, given only knowledge of the head-to-head probabilities.
EDIT:
The problem is that the three-way win probabilities depend not just on the average abilities of the horses, but also on how reliable they are. A horse that's very unreliable (sometimes runs really fast and sometimes runs really slow) will generally do better in a 3-way race than in a 2-way race, because if they run really fast against one of their opponents they'll run really fast against both of them! Notice that my three horses all finish the course in the same amount of time on average, but horse A still wins out by being unreliable.
In short, if you want to calculate 3-way win probabilities, then you'll need to either know or assume something about how a horse's performance varies, as well as about its average performance. There's no way to get this data from 2-way win probabilities.
Assume that you have an algorithm to find the first three places in 6 races. Assume that after the fifth race $n$ horses have raced.
If $n=25$, then the last race can detemine only the winner, but not the second nor the third place: it has to race one horse from each previous race, so if the first three places were all in the same heat or 1,2 in the same and 3 in a different, it couldn't tell the difference.
So $n<25$, and in the last race you have to race the new horses against the first three places A1, A2, A3 (possibly without knowing the order) of the $n$ horses that already have raced, otherwise you cannot determine the overall three fastest horses with the last race.
Hence $n=23$ or $n=24$.
If you assume $n=23$, then it is impossible to determine the three fastest horses out of 23 with 5 races:
You cannot have less than three different winners, since only two repetitions are allowed.
If you have three different winners that have not been compared, then any of the 5 second places could be A2 or A3.
If you have four or more different winners that have not been compared, all of them could be A1,A2, or A3.
If $n=24$, then you have to know a set of four horses out of the first 24 which contains A1,A2 and A3. But this is impossible in 5 races, since you have at least 4 different winners that have not been compared, and so these four horses and the second places could be all A1,A2 or A3.
Hence all cases lead to a contradiction, and so the assumption that 6 is enough, is untenable.
Best Answer
First let's show that it's possible to do this in $7$ races.
Group the $25$ horses into $5$ groups of $5$ and race them. The 4th and 5th place horses of each race cannot possibly be one of the three fastest. We are left with $15$ horses.
Let us label these remaining horses, using a $6$th race to help us. Race the fastest horse from each of the first $5$ races, and then label the races from $a$ to $e$ based on the finishing position of the corresponding fastest horse, with the horse from race $a$ being the fastest. Let $h_n$ represent a horse in race $h$, finishing in $n$th place.
Clearly, horse $a_1$ is the fastest horse of all. We also know that $a_1$ beat $a_2$ and $b_1$. No other horse can possibly be in overall position $2$ because one of these horses finishes between them. $a_2$ beats $a_3$, and $b_1$ beats $b_2$ and $b_3$, as well as every horse in races $c$ through $e$.
Similarly, the only horses that can be in overall position $3$ are $a_2$, $a_3$, $b_1$, $b_2$, and $c_1$. These are the horses that could possibly have no horses in between it and position $2$.
All we have to do left is race those $5$ ($a_2$, $a_3$, $b_1$, $b_2$, and $c_1$) and you'll have the fastest three.
Now let's prove that $7$ races is optimal.
Using the same idea, we can draw a directed graphs to represent these races and relations. The circles or nodes are horses, and the directed paths represent one horse being faster than another. Here would be what one race would look like, with the fastest horse on the left:
$$ \circ\rightarrow\circ\rightarrow\circ\rightarrow\circ\rightarrow\circ $$
So basically, what we want to end up with to find the three fastest horses is a parent node and a total of at most $5$ children with a depth of $2$ from this parent, with all of the other nodes being under $5$ children. We need a race to compare these $5$ children, and the other races to set up the graph. Each race will place $4$ horses, as the fastest horse needs to be a horse that has already raced in order to be compared. The only exception is the first race, which can place $5$. $\lceil 24/4 \rceil = 6$, and we add that to our check race to show that the best possible solution is $7$ races, and it can in fact be attained.
EDIT: I fixed the errors hopefully. I'll continue to fix the proof as needed.