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 $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|cite|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
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
This was asked and not answered at… 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
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
@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

Your Answer


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

Browse other questions tagged or ask your own question.