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

• You'll need at the very least $\log(25!)/\log(5!)\gt12$ runs. – joriki Oct 9 '12 at 10:37
• Use stopwatch and then 5 runs are enough.. – Berci Oct 9 '12 at 11:15
• You seem to have a transitive tournament on 25 nodes, do not know the edge directions, and are sampling 5-vertex induced subgraphs until you find all the edge directions. It might be that a "dynamic" scheme (where we can adjust our decisions based on knowledge of earlier partial rankings) might be better than a "static" scheme; is this allowed? – Douglas S. Stones Oct 9 '12 at 13:17
• Finding the top three horses was (will have been? it's a later question...) discussed at math.stackexchange.com/questions/56159/number-of-races-needed – Gerry Myerson Jan 24 '13 at 3:13
• With $k=2$, this is problem is actually equivalent to a standard sorting algorithm. quicksort is I think the best one and runs in $n\log_2n$. – Tom-Tom May 7 '15 at 9:35