How to find a total order with constrained comparisons

There are $25$ horses with different speeds. My goal is to rank all of them, by using only runs with $5$ horses, and taking partial rankings. How many runs do I need, at minimum, to complete my task?

As a partial answer, I know that is possible to determine the first $3$ horses with $7$ runs, and, by a slight generalization of the optimal algorithm used to find the first three, have the complete ranking in $20$ runs.

Is it possible to do better?

What if we have $n$ horses and want to rank them with runs with $k$ horses?

Solution 1:

Just some lower and upper bounds.

There must be at least $13$ races, because you need $25!$ possible results, all the possible orderings of the $25$ horses - and there are only $120=5!$ results in each race. Since $120^{12}<25!<120^{13},$ you definitely cannot do it in $12$ races.

With $n$ horses and races of $k$ horse, you need at least: $$\left\lceil \log_{k!}(n!)\right\rceil$$ races.

(When $k=2,$ this is the usual minimum of $\log_2(n!)\approx n\log_2 n-n$ comparisons to do a complete sorting of a list.

It can definitely be done in $30$ races, by considering all 30 lines in the finite affine plane $\left(\mathbb Z/5\mathbb Z\right)^2.$ That is definitely overkill - every horse is raced against every other horse.