Worst case 20 races, best case 13 races
Run all 25 horses in 5 races to get the following partial order, with each letter corresponding to a horse's completion time (which we assume for simplicity to be constant for each horse regardless of the number of races run).
a < b < c < d < e
f < g < h < i < j
k < l < m < n < o
p < q < r < s < t
u < v < w < x < y
Call these the initial 5 chains. The best of these are afkpu
, whose relative order we don't yet know. We repeatedly race the fastest horses with unknown relative order against each other. Sometimes, fewer than 5 horses would be required, in which case we put in the next fastest of some of the chains.
Race 6 ('best of the best'): afkpu
Assume without loss of generality that a < f < k < p < u
. The fastest horse is then a
. Remove a
from the pool (of horses that must still compete) and continue.
Race 7 ('runners up'): bfcgk
From the initial 5 chains and race 7, we know the next fastest horse is one of bf
. The fastest horse after that would either be the other (of bf
) or one of cgk
; all other horses are slower than these 4. The winner and runner up of race 7 are awarded positions 2 and 3, and then removed from the pool.
Consider the initial 5 chains. In each chain, the remaining horses still form a single chain, so we still have 5 chains, though some will have fewer than 5 horses. Repeat the 'best of the best' and 'runners up' races to get 3 horses every two races (thanks @IvoBeckers). When there are at most 5 horses remaining in the pool, run them all in a single race to determine the bottom 5 positions.
Calculations: races 1-5 yield no positions, the first 21 positions are determined in the next 14 races, and the last race determines the final 4 positions. Total 5 + 14 + 1 = 20 races in the worst case.
Best case: use the above method, but assume the most convenient winning pattern possible to get more than 2 placings per race after race 6.
Race 6: afkpu
, a=1
.
Race 7: bfcgk
, b=2,f=3,c=4
. After bf
are removed, the fastest 3 horses according to the established partial orders are cgk
, all of which are in race 7, so we get 3 placings from this race. Assume g < k
since we're looking for the best case.
Race 8: dgehk
, d=5,g=6,e=7
. We only really need dg
for the 'best of the best', so we have room for 3 more - choose ehk
. This race now also has the composition of a 'runners up' race, so we get 2 placings dg
. In the best case, e
also places, and all the remaining horses in the pool are slower than either h
or k
.
Race 9: hkilp
, h=8,k=9,l=10
. We don't need a 'best of the best' race since hkpu
are already ordered, so this is just a 'runners up' race. In the best case, hk
take out the next 2 placings, and we get a bonus placing since the remaining pool is slower than at least one of ilp
.
Race 10: impjn
, i=11,j=12,m=13
. The 'best of the best' only needs to sort imp
, so we have room for 2 more - choose jn
. If ij
are fastest in this race, the remaining pool is slower than at least one of mp
.
Race 11: npoqu
, n=14,p=15,o=16
. The 'best of the best' only needs to sort np
; add oqu
. If np
are fastest in this race, the remaining pool is slower than at least one of oqu
.
Race 12: qurvs
, q=17,r=18,u=19
. The 'best of the best' race is not needed.
Race 13: svtwx
, s=20,t=21,v=22,w=23,x=24,y=25
. Last 6. Race all except one of the last in its chain (say, y
). If the loser of race 13 (say x
) is also in that chain, the chain places the remaining horse last (we already know x < y
).