# 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?

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.