39
$\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 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?

$\endgroup$
  • 4
    $\begingroup$ You'll need at the very least $\log(25!)/\log(5!)\gt12$ runs. $\endgroup$ – joriki Oct 9 '12 at 10:37
  • 4
    $\begingroup$ Use stopwatch and then 5 runs are enough.. $\endgroup$ – Berci Oct 9 '12 at 11:15
  • 1
    $\begingroup$ 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? $\endgroup$ – Douglas S. Stones Oct 9 '12 at 13:17
  • 2
    $\begingroup$ 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 $\endgroup$ – Gerry Myerson Jan 24 '13 at 3:13
  • 2
    $\begingroup$ 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$. $\endgroup$ – Tom-Tom May 7 '15 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.