0

You have 25 horses and a track that can race 5 horses at a time. You don't know their times but can see their speed relative to other horses. What is the least possible amount of races to find the fastest 5 horses.

My thought process is I race 5 of them in order and (for simplicity's sake) get 1,6,11,16,21 as the fastest of each group. Then for the 6th race, race these 5 and get them in order again for simplicity's sake. We now know that 1 is the fastest of all horses. For the 7th race I would race 3,7,11,12,16 to try and get information on other horses knowing that 2 or 6 will be guaranteed to be in top 5. But when I begin casing it out, I get confused. Any help or insight would be appreciated.

Edit: Similar problems were considered , for example

(rank all horses) How to find a total order with constrained comparisons

(top 3 horses instead of top 5) Why $6$ races are not sufficient in the $25$ horses, $5$ tracks problem

Not the same as top 3 as racing 2,3,6,7,11 is insufficient for top 5 as the case of 6,7,11,2,3 requires 2 extra races and I believe (might be wrong) that this can be done in 8. I am just not sure which horses are required for race 7.

festiveo
  • 1
  • 1
    You're on the right track. This is a classic puzzle - try a web search. – Karl Oct 20 '23 at 19:36
  • 2
    @Karl The classic web puzzle is 3 horses and would just be 7 races, racing 2,3,6,7,11 for possible top 3. There isn't a solid answer online for the case with getting the top 5. – festiveo Oct 20 '23 at 20:08

1 Answers1

0

Let the top 5 horses be $t_1,\ldots, t_5$.

If you do your first 6 races as described you can use grid to represent horses with a horse $h$ receiving a pair (i,j) if $h$ came i-th in the first race it participated, and and if the winner of that race was j-th in the sixth race. This is slightly different from you notation, but you get $n=i+5(j-1)$, e.g. 1=(1,1) and 22=(2,4) in new notation.

After 6th race you know that $t_1=(1,1)$, i.e. (1,1) is the fastest, but also you know that if i+j>6, then (i,j) is not in top 5. For example, (3,4) is not in top 5 as you have sequence of horses faster than it (3,4)-(3,3)-(3,2)-(3,1)-(2,1)-(1,1). So you identified 1 horse from top 5 and you still have 14 candidates for other four spots in top 5 (14 pairs with 7>i+j>2).

For 7th race I suggest (2,1); (3,1); (1,2); (2,2); (1,3). Note that two top horses are among this quintuple, so you identified say $t_2,t_3$. Also, consider two losers $l_1<l_2$ of this quintuple, then $l_1$ is not in top 5, but $l_2$ can be. What is important is that all horses that have both coordinates at least as large as those of $l_1$ (or $l_2$) are not in top 5. For example, if $l_1=(1,3)$, $l_2=(2,2)$, then horses that are not in top 5 are (1,4),(1,5),(2,4),(3,2),(3,3) for $l_1$ and additionally (2,3),(2,4) for $l_2$ (note that say (2,4) can be eliminated by both $l_1,l_2$). You can check by considering cases for $l_1$ and $l_2$, that they together always eliminate at least $7$ horses. Together with $l_1$ at this stage you eliminated $8$ horses. You also identified $t_1$ and $t_2$, so there are $14-8-2=4$ candidates for other 2 spots in top 5.

Finally you check those candidates in 8th race with any other horse. I wonder if doing so in 7 races is possible.

C614
  • 685
  • 1
    Thank you for the in depth response. However, I was curious what you thought if the race ended with losers (2,1) and (3,1). Wouldn't you then have too many horses to race? Even knowing t 1 and 2 are (1,2) and (1,3) wouldn't be enough assuming this worst case race. – festiveo Oct 21 '23 at 22:36
  • You have a point, I made mistake considering cases. So maybe we can do it in 9 races. After 7th race (as described) we should have at most 8 candites. Those candidates would be 14-2(winners in race 7)-1(loser $l_1$ in race 7)-3(min number of additional eliminated cases). Among those 8 we need fastest 2, which can always be done in 2 extra races. – C614 Oct 22 '23 at 03:14