45
$\begingroup$

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?

  • 2
    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$.2015-05-07

0 Answers 0