MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## There are n horses. At a time only k horse can run in the single race. How many minimum races are required to find the top m fastest horses?

There are n horses. At a time only k horse can run in the single race. How many minimum races are required to find the top m fastest horses? Please explain your answer. (There is no timer.)

The $n = 25, k = m = 5$ case was a Google interview question and there are various answers on the web. But I am not sure what should be the right answer for this. Any ideas?

-
Try math.stackexchange instead f MO. – Misha Nov 30 at 16:33
@Misha: I have already posted the MSE link. – Debanjan Chanda Nov 30 at 16:44
This seems like a nontrivial algorithms question to me. It may be a standard result for the right people, but I don't think it is obvious and I would be interested in learning the answer. Voting to reopen. – David Speyer Nov 30 at 20:43
If $k=2$, this is a well studied but not solved problem en.wikipedia.org/wiki/Partial_sorting . I have to assume that someone knows something about larger $k$. – David Speyer Dec 1 at 0:32
@David: This is even weaker than partial sorting, since we don't need to know the exact rank of elements $1$ to $m$, just the set of elements in those positions. – Zack Wolske Dec 2 at 23:37