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

  • 3
    You'll need at the very least $\log(25!)/\log(5!)\gt12$ runs.2012-10-09
  • 4
    Use stopwatch and then 5 runs are enough..2012-10-09
  • 1
    You seem to have a [transitive tournament](http://en.wikipedia.org/wiki/Tournament_(graph_theory)#Transitivity) 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?2012-10-09
  • 0
    Yes, dynamic schemes are allowed, and, in fact, my solution in 20 runs is dynamic.2012-10-09
  • 1
    I have an update. If we start with 5 runs with all the 25 horses, and at least 2 of the first 4 horses run together in one of the 5 initial runs, we can find the first 5 horses with 8 runs only. This leads to an adaptive algorithm that gives the complete ranking in about 18.5 runs (average), 20 runs (worst).2012-10-09
  • 2
    Finding the top three horses was (will have been? it's a later question...) discussed at http://math.stackexchange.com/questions/56159/number-of-races-needed2013-01-24
  • 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