Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.