Tell me more ×
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.
up vote 4 down vote favorite
2

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
More generally, you certainly require at minimum $\log_{k!}\binom{n}{m}$ races. That's because a race of $k$ horses yields the same result as approximately $\log_2{k!}$ pairs of horses. – Thomas Andrews Nov 30 '12 at 16:12
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 at 13:21
show 2 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

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.