There are $n$ horses. At a time only $k$ horses can run in a single race. What is the minimum number of races required to find the $m$ fastest horses? The following question was asked and not (yet) answered at Math Stack Exchange.

There are $n$ horses. At a time only $k$ horses can run in the single race. What is the minimum number of races required to find the top $m$ fastest horses? Please explain your answer.

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 the right answer should be for this. Any ideas?
 A: 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 (3k-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$.
