6
$\begingroup$

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.

  • 0
    If $k=2$, I think a lower bound for the number of races is $\log_2\binom {n}{m}$.2012-11-30
  • 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?2012-11-30
  • 3
    This was asked and not answered at http://math.stackexchange.com/questions/209790/how-to-find-a-total-order-with-constrained-comparisons The $n=25, k=m=5$ case was a Google interview question and there are various answers on the web.2012-11-30
  • 0
    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.2012-11-30
  • 0
    Stan Wagon (in his PoW e-mail) said he had written a paper on this subject with Stephen Morris and Richard Stong which was to be published in Math Horizons, but I don't find it online.2012-11-30
  • 0
    @RossMillikan Actually, it looks like the older question wants a complete ranking, not just a list of the top $5$ horses. (Note, the OP doesn't even ask for a ranking of the top $m$, just a list of them. If $m=n$, then it takes $0$ races, and if $n=m-1$ you can do it in $\frac{n-1}{k-1}$ races.2012-11-30
  • 2
    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 :-)2013-01-19
  • 1
    @RossMillikan Now the [Math Horizons article of Morris, Stong and Wagon](http://www.jstor.org/stable/10.4169/mathhorizons.20.4.20) has been published, but is not available for free.2013-09-11

0 Answers 0