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 $n$ horses. At a time only $k$ horses can run in the single race. How many minimum races are required to find the top $m$ fastest horses? Please explain your answer.

PS: There is no timer.

share|improve this question
    
If $k=2$, I think a lower bound for the number of races is $\log_2\binom {n}{m}$. –  Thomas Andrews Nov 30 '12 at 15:55
4  
I suppose we have no timer? I.e. any race can only give an ordering of the participating horses, and not information about exactly how fast they actually are? –  malin Nov 30 '12 at 15:59
3  
This was asked and not answered at math.stackexchange.com/questions/209790/… The $n=25, k=m=5$ case was a Google interview question and there are various answers on the web. –  Ross Millikan Nov 30 '12 at 16:10
1  
It's interesting that no-one has bothered to mention the rather unrealistic assumption that the horses always run the race in exactly the same time :-) –  joriki Jan 19 '13 at 13:21
1  
@RossMillikan Now the Math Horizons article of Morris, Stong and Wagon has been published, but is not available for free. –  pepan Sep 11 '13 at 16:53
show 3 more comments

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.