A well-known puzzle goes:

"Suppose that you have 25 horses and a racetrack on which you can race up to 5 horses. If the outcome of each race only tells you the relative speeds of the horses in the race, how many races do you need to determine the fastest 3 horses (and what is the strategy)?"

The solution (look away now if you don't want a spoiler) is to arrange the horses into groups of five and race them, labeling the horses $a_1,\dots,a_5$, ..., $e_1,\dots,e_5$ -- for example, the horse in position 3 in the second race gets the label $b_3$.

Then race horses $a_1, b_1, c_1, d_1, e_1$, and relabel the horses so that all those in the same group as the winner of this race get the label $a_j, j=1,\dots,5$ and so on. Finally, race horses $a_2, a_3, b_1, b_2, c_1$ -- the three fastest horses are now $a_1$ and the two fastest from the final race.

The question: Does this strategy generalize to $m$ horses and $n$ tracks where you want to find the fastest $k$ horses?


Well, this particular strategy generalizes for finding the k best horses when the track size is $n = (k-1)(k+2)/2$ and the number of horses is $n^2$, and it takes n+2 races as in your example:

Split them into n groups of size n, race them in those sets, and label as $a_{11}, a_{12}, \dots, a_{1n}, a_{21}, a_{22}, \dots, a_{2n}, \dots, a_{nn}$ as before (so the horse who came in $j$th place in the $i$th race has label $a_{ij}$. Then race $a_{11}, a_{21},\dots,a_{n1}$, and relabel the first subscripts of all horses using the results of this race. The winner of that race is the best horse. To determine the other k-1 best horses, race the n other horses who have fewer than k horses that are better than them (directly or by transitivity): $a_{12}, a_{13}, \dots, a_{1k}, a_{21}, a_{22}, \dots, a_{2(k-1)}, a_{31}, a_{32}, \dots, a_{3(k-2)},\dots, a_{k1}$. (Note here that conveniently $n = (k-1) + (k-1) + (k-2) + (k-3) + \dots + 2 + 1 = (k-1)(k+2)/2$.)

But this still leaves open the question of what to do for other cases.

  • $\begingroup$ And by induction, for $n^r$ horses, $n^{r-1}+n^{r-2}+\cdots+n+r=(n^r-1)/(n-1)+(r-1)$ races are sufficient. $\endgroup$ – Thomas Kalinowski Jul 1 '11 at 20:14

protected by Community Jun 19 '18 at 10:19

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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