## Generalization of a horse-racing puzzle

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?

-
 Under math.uiuc.edu/~west/regs/ksetsort.html the general problem is stated formally. – Thomas Kalinowski Jul 1 2011 at 18:41

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.

-
 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. – Thomas Kalinowski Jul 1 2011 at 20:14

I don't understand why you would run an extra race for the other 2 positions. In your 25 horse, 5 track example, you can calculate the relative speed of all horses immediately after the 6th race.

-
Your comment is just wrong, perhaps because you've misunderstood the question. Each running of a race gives you relative information about the rates of the five horses in it, but no information about their relative rates as compared with the other 20 horses (unless such is conveyed by transitivity). After the sixth race, there is no way to know which of $a_2$ and $b_1$ is faster, for example. (All we know is that both have lost to $a_1$.) – JBL Jan 25 2011 at 15:14
I assume each horse runs at a fixed (but initially to us, unknown) speed. So this is a sorting problem involving 25 unknown numbers. Otherwise you have to define "fastest": is it average speed over X races? the maximum speed obtained over X races? Because your algorithm eliminates the 2 slowest horses in a race which prevents them from attempting to post a faster speed in a later race. With my assumptions then, after 5 races of 5 horses, you have the relative speed of all horses with respect to either a1, b1, c1, d1, or e1. Then you race a1, b1, c1, d1, and e1 to obtain speeds wrt (eg) a1. – X Xunzis Jan 29 2011 at 0:16
And yes you know the relative speed between a2 and b1 because a2 had raced a1 previously and a1 has raced b1 in the 6th race. Each race gives you relative speed not just relative position. – X Xunzis Jan 29 2011 at 19:21
By "relative speed" it was meant that you get a relation $v_1 > v_2 > \cdots > v_5$ after the race, not that you can express the speeds $v_2,\dots,v_5$ as multiples of the speed $v_1$. – Chris Taylor Feb 2 2011 at 15:58

I don't know about the generalization, but I found a great explanation over here for the 25 horses puzzle:

25 horses puzzle

-