Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
You'll need at the very least $\log(25!)/\log(5!)\gt12$ runs. –  joriki Oct 9 '12 at 10:37
3  
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
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). –  Jack D'Aurizio Oct 9 '12 at 16:24
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.