Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
2  
@Misha: I have already posted the MSE link. –  Debanjan Chanda Nov 30 '12 at 16:44
2  
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 '12 at 20:43
6  
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 '12 at 0:32
6  
I just wanted to say that this is the same as Generalization of a horse-racing puzzle. –  Dpiz Dec 24 '13 at 23:02
5  
It isn't clearly stated whether we have to plan all the races in advance or we can plan each race after knowing the results of the previous races. The answer could change. –  Brendan McKay Dec 25 '13 at 1:36

1 Answer 1

A trivial lower bound is $n/k$, since clearly every horse must race to obtain the answer.

I think we can get $O(n/k)$ upper bound, by adapting the median-of-medians selection algorithm.

First, note that, up to a constant factor, this problem is equivalent to finding the $m$th best horse. For the reduction one way, simply find the $m$ best horses and the $m-1$ best horses and see which horse mysteriously disappeared. For the reduction the other way, find the $m$th best horse, then race every other against it to find which are better and which are worse. (In fact, you don't need to do this - it's not hard to check that if you've found the $m$th best horse through repeated racing, you already know which are better and which are worse.)

For $k=2$, the median-of-medians algorithm is known to give an $O(n)$ time bound, as was pointed out by Ralph Furmaniak. We will also use this to handle $k\leq 4$.

So assume $k\geq 5$ and is odd. Let $T(n)$ be the time it takes to find the $m$th horse among $n$ horses. Then divide the horses into groups of $k$, race them in time $n/k$, and take the median of each. Then select the median of those medians in time $T(n/k)$, and pivot on it in time $n/(k-1)$. (to pivot, the pivot horse must race each other horse only once. This allows us to remove at least $n(k+1)/4k$ of the horses, so we can find the $m$th horse in time $T(n (k+1)/4k)$. So we get:

$$T(n) \leq T\left(\frac{n}{k}\right) + T\left( \frac{n(3k-1)}{4k}\right) + \frac{n}{k}+\frac{n}{k-1} $$

By induction,

$$T(n) \leq \frac{4k}{k-3} \cdot \left( \frac{n}{k}+\frac{n}{k-1} \right) = O \left(\frac{n}{k}\right)$$

In fact we obtain an explicit constant of $8+o(1)$.

This ignores non-unique divisibility, which should only lead to a small error term unless $k$ is very large as a fraction of $n$.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.