Don’t Hold Your Horses: Race ’em!

You have 25 horses and want to know which are the three fastest. Whenever you race horses, the order of finish accurately reflects the relative speeds of the horses but you can only race five at a time. What’s the minimum number of races required to determine the three fastest, and how do you do it?

Communicated by D. Stone.

46 Comments

  1. Steven Miller on November 10, 2012 at 4:37 am

    curran: correct



  2. Steven Miller on October 6, 2012 at 12:57 am

    well done (sjm1 AT williams.edu)



  3. Steven Miller on July 5, 2012 at 1:54 pm

    You can do it in less…. sjm1 AT williams.edu



  4. Vedad on July 5, 2012 at 9:20 am

    10 times



  5. Steven Miller on July 5, 2012 at 2:06 am

    sure — sent //s



  6. javier on July 5, 2012 at 1:45 am

    i got a 11 but i think i can do it in less, send me a hint pls



  7. Steven Miller on June 26, 2012 at 1:18 am

    you can do in less than 11



  8. Chris on June 25, 2012 at 9:44 pm

    Answer: 11
    Rationale: Run your first race of 5 horses. Take the top 3 from that race and take 2 of the remaining 20 horses (25 minus 5) and race them against the top 3 from the previous race. Repeat the process for 9 more races until you have raced all 25 horses and determined your top 3 horses.



  9. Steven Miller on June 15, 2012 at 1:08 pm

    thanks! /.s



  10. Monique on June 15, 2012 at 9:57 am

    you did post this (someones solution) =)



  11. Steven Miller on May 13, 2012 at 1:28 am

    Good start, but I can do in less than 10 — email me at sjm1 AT williams.edu if you want to chat more ..s



  12. Heo on May 12, 2012 at 5:50 pm

    I’m sorry, but it looks like I had a typo in my previous post. So call it race 8 instead of 9 and 9 instead of 10. So 9 is the miminum amount of races that we need to do to be sure.



  13. Heo on May 12, 2012 at 5:45 pm

    You begin with racing all the 25 horses in pulls of 5, which then takes 5 races and now you have the potential 5 best candidates.

    Then you do a 6th race with those 5 horses and you have the potential 3 fastest horses, although you cannot be sure yet that those are the fastes because there might be some very fast horses who got stuck in the group with the fastest in one of the 5 races.

    Then you will do a 7th race with the horses who came in as number 2 in the first 5 races and then find the 2 best from this pull (Because the fastest in the 6th race is the fastest horse, that we know.)

    Then we do a 9th race with all the horses who came in as number 3 in the first 5 races and find the fastest of those horses (Who knows, might be a very fast unlucky horse who came in the group with both the fastest and the second fastest in one of the 5 first races).

    Now we will do the finale race (race 10) with the 2 who came as number 2nd 3rd in the 6th race + the 2 who came as number 1 and 2 in the 7th race + the 1 who came in first in the 9th race and from this race we will take the 2 fastest horses and now we know who is the fastest horse (The one who won race 6) and the 2nd and 3rd fastest as well.
    So I believe 10 is the minimum amount of race you need to do to KNOW for sure you have the 3 fastest horses.

    Is this correct? Seems to me that this is the minimum amount of races that needs to be done, just want to check to be sure :p



  14. Steven Miller on March 30, 2012 at 5:16 pm

    you can do in less than 11.



  15. scott on March 30, 2012 at 5:13 pm

    race 5 horses, keep top three to race again right away, twenty horses remain unraced, keep top three from race one and add in two and re race keepingtop three, repeat with remaining horses, so initial race, plus ten more, is teh answer 11? I am new to site and do not have a math backround but i try to think and use scrap paper, i need a mathbackround with formulas to get better?



  16. Steven Miller on March 22, 2012 at 4:50 am

    Sam: that’s the smallest number I can do as well. //s



  17. Steven Miller on March 11, 2012 at 1:43 am

    good, but it can be done in fewer….



  18. Alejandro on March 10, 2012 at 9:54 pm

    Run 5 races of 5 horses each. Keep record of top 3 from each race. Race all seconds. The candidates to be in the top three are the 5 first horses. The first second and the third horse from the same group as the first second. Seven horses left. Run any five. Then run the top three with the remaining two horses and you have the top three. That makes 8 races.



  19. Steven Miller on February 21, 2012 at 1:25 am

    Dennis: correct — not posting as its the soln.



  20. Steven Miller on January 10, 2012 at 4:59 pm

    Nice; however, you can do it in less than 9.



  21. Mike B on January 10, 2012 at 4:56 pm

    9 Races total.

    The first 5 races (i’ll refer to them as the original races) are used to gear the speeds of every horse (for example 1-5 race, 6-10 race, 11-15, 16-20, 21-25 race). The 3 possible scenarios are: the top horse from 3 of the 5 original races are the fastest, the top 2 horses from 1 original and top horse from another original race are fastest, or the top 3 horses from 1 original race are the fastest.

    Once establishing the positions of the horses, all of the horses in 1st place from the original races will race each other. All of the 2nd place horses from the original races will race each other, and all of the 3rd place horses from the original races race each other. This will eliminate 2 first place horses, 4 2nd place horses and 4 3rd place horses.

    In the final race, we wont need to race the winner of the 1st place race (since we know that horse is definitely in the top 3). The 2nd and 3rd place horses from the 1st place race and the 1 place horse of the 2nd place race, and the 1st place horse of the 3rd place race will go against each other. The top 2 horses from that race along with the top horse (that didn’t have to race) are the 3 fastest. Hopefully I worded that in a way that makes sense haha. At least it makes sense in my head!



  22. Steven Miller on January 6, 2012 at 5:20 am

    Bren: correct, well done; not posting as it’s the soln.



  23. Steven Miller on November 23, 2011 at 2:42 am

    you can do in under 9 — let me know if you want a hint



  24. Steven Miller on November 23, 2011 at 2:31 am

    you can get the order of the horses in each race, but I don’t see how you do 6 — can you email me at [email protected]



  25. Josh H on November 23, 2011 at 1:45 am

    PS, i haven’t looked at the comments yet in case the answer is in them.
    Wouldn’t the smallest number you can do it in be 10-11 races
    because you would obviously start by splitting the 25 into 5 groups, and take the top 3 from each group. You now have your 15 fastest, so split that into 3 groups of five and take the top 3 from each group, leaving you with your 9 fastest. you have now raced a total of 8 times. Here is where things get tricky, first race five horses and set the fastest 3 aside. now take the fastest from group A and place it with the four in group B and race them. IF the fastest from group A does not place amongst the top 3 in the second race, that fastest three in that race are your fastest. If the fastest in group A does place among the top 3, you must take those 3 and race them with your previous 2, and the top three of that race are your fastest.



  26. Viv on November 22, 2011 at 9:40 pm

    umm ok is it 6( if u can see who is 1st and 2nd etc) or is it 8 ( if u can only see the wingng horse)



  27. Steven Miller on November 11, 2011 at 10:49 pm

    not quite, you can’t use a race with all the second fastest….



  28. Steven Miller on November 11, 2011 at 10:43 pm

    we want more than just hte winner, we want the top three



  29. mr.man on November 11, 2011 at 2:21 pm

    Well you can run 5 horses in a race so when you run all the horses it leaves you with 5 winners and race those winners to get your winner which is 6.



  30. Steven Miller on November 4, 2011 at 3:42 am

    You’re on the right track. Who do you run in the 6th race?



  31. mr.man on November 3, 2011 at 11:03 pm

    let’s see um 25 horses divided by the first 5 races so 25/5=5 so it takes 5 to get your top 5 horses so now you have 5 horses therefore you run them again once to see the top 3 IT’S RIGHT!



  32. Steven Miller on October 3, 2011 at 1:35 pm

    No, you only know the order in which they arrive.



  33. Mads on October 3, 2011 at 11:52 am

    Ids it possible to record time?



  34. Anonymous on October 3, 2011 at 11:51 am

    If we can record time, we can do it in 5 races itself.



  35. Steven Miller on October 1, 2011 at 3:00 am

    it is possible that the 3 fastest are in the same heat, but you can do it in fewer than 8



  36. Harsh on October 1, 2011 at 2:14 am

    I also got 8…is 7 even possible?!?! can i have the solution, because i don’t see how to get less than 8, because you need minimum 5 heats and then 3 more of the best horses just in case all the 3 fastest were in the same group of 5.



  37. Steven Miller on September 26, 2011 at 2:36 am

    Maybe — I’ve never seen a soln with 6 so I don’t know.



  38. zak on September 25, 2011 at 5:38 pm

    The people who are saying six are not accounting for the possibility that one of the initial groups of five may contain more than one top three horse.



  39. Steven Miller on June 19, 2011 at 1:31 am

    I would **LOVE** to see how you get 6; the best I can do is 7. You can email me at sjm1 AT williams.edu.



  40. ty on June 18, 2011 at 9:28 pm

    İ say 6 . were do i go wrong ?



  41. Steven Miller on June 16, 2011 at 3:16 am

    You’re close. One can do better than 8 — I’ll send you an email. //s



  42. Joe G on June 15, 2011 at 5:29 pm

    I’m for sure you can do it with 8. However I bet 7 is possible… and I have no idea if 6 is possible, and have no idea for it, so I’ll say no.

    What I have done so far is race 5 heats with all the horses and take the top 3 of all.

    Then take the 1st place horses of the 5 heats and race them against each other, and then take the top 3 out of those. Then of the top 2 horses in the 3, take the 2nd place horses in their original heat and then race those 5.

    This I thought would give the best top 3, however if the actual top 3 were in the same initial heat in the beginning, then you would have to do one more, making 8 races total.

    Unless you can use deductive reasoning… but my way doesn’t let that I believe…

    Whatcha think?



  43. Steven Miller on May 11, 2011 at 8:10 pm

    not quite.



  44. AK on May 10, 2011 at 6:59 pm

    Race five heats and select best out of each heat – 5 fastest. (Qualifies for the finals)
    Race the finalist and you get the fastest three. (1st, 2nd and 3rd)
    Therefore, 6 Possible Races.



  45. Steven Miller on May 3, 2011 at 3:12 am

    This is the best I have. One cannot do it in 5; is 6 possible?



  46. Anonymous on May 2, 2011 at 3:27 pm

    race with five heats and record the times. and then choos ethe fastes three



Leave a Comment