Generalization of a horse-racing puzzle - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T07:03:46Z http://mathoverflow.net/feeds/question/50737 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50737/generalization-of-a-horse-racing-puzzle Generalization of a horse-racing puzzle Chris Taylor 2010-12-30T16:48:54Z 2011-05-26T08:03:02Z <p>A well-known puzzle goes:</p> <p>"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)?"</p> <p>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\$.</p> <p>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.</p> <p>The question: Does this strategy generalize to \$m\$ horses and \$n\$ tracks where you want to find the fastest \$k\$ horses?</p> http://mathoverflow.net/questions/50737/generalization-of-a-horse-racing-puzzle/50742#50742 Answer by Jonah Ostroff for Generalization of a horse-racing puzzle Jonah Ostroff 2010-12-30T17:30:21Z 2010-12-30T17:30:21Z <p>Well, this <em>particular</em> 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:</p> <p>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\$.)</p> <p>But this still leaves open the question of what to do for other cases.</p> http://mathoverflow.net/questions/50737/generalization-of-a-horse-racing-puzzle/53179#53179 Answer by X Xunzis for Generalization of a horse-racing puzzle X Xunzis 2011-01-25T03:32:04Z 2011-01-25T03:32:04Z <p>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.</p> http://mathoverflow.net/questions/50737/generalization-of-a-horse-racing-puzzle/66028#66028 Answer by Steve for Generalization of a horse-racing puzzle Steve 2011-05-26T08:03:02Z 2011-05-26T08:03:02Z <p>I don't know about the generalization, but I found a great explanation over here for the 25 horses puzzle:</p> <p><a href="http://www.programmerinterview.com/index.php/puzzles/25-horses-3-fastest-5-races-puzzle/" rel="nofollow">25 horses puzzle</a></p>