Generalization of a horse-racing puzzle - MathOverflow

Generalization of a horse-racing puzzle

2010-12-30T16:48:54Z

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?

Answer by Jonah Ostroff for Generalization of a horse-racing puzzle

2010-12-30T17:30:21Z

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.

Answer by X Xunzis for Generalization of a horse-racing puzzle

2011-01-25T03:32:04Z

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.

Answer by Steve for Generalization of a horse-racing puzzle

2011-05-26T08:03:02Z

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

25 horses puzzle