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).
13

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? Please explain your answer. (There is no timer.)

This was asked and not (yet) answered at math.stackexchange.

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?

flag
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
1 
 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
3 
 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
show 2 more comments

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.