mersenneforum.org Horse Race
 Register FAQ Search Today's Posts Mark Forums Read

 2003-08-30, 13:15 #1 Gary Edstrom   Oct 2002 5×7 Posts Horse Race There are 25 horses which all run at different speeds. A faster horse always beats a slower horse. You can race 5 horses at a time. What is the minimum number of races needed to determine the three fastest horses in order from fastest to slowest? There are no ties and you may not time them.
 2003-08-30, 13:49 #2 Fusion_power     Aug 2003 Snicker, AL 7·137 Posts I had to study this a few minutes, the horses part is just a distraction. All it really is in the end is a sorting algorithm. After 6 races you will have identified the fastest horse. From that I derived the probable answer and it is much lower than I initially guessed. I'll wait till others have a look before posting it.
 2003-08-30, 17:28 #3 tom11784     Aug 2003 Upstate NY, USA 14616 Posts I have an answer as well, and it seems too low to be improved upon.
2003-08-30, 17:37   #4
axn

Jun 2003

3×11×157 Posts

Quote:
 Originally Posted by tom11784 I have an answer as well, and it seems too low to be improved upon.
same here

 2003-08-30, 19:41 #5 Wacky     Jun 2003 The Texas Hill Country 21018 Posts Well, let's set some bounds. First, a easy upper bound is 11 races. There are 25 horses to start. To start, for each race, you can pick any 5 horses from the paddock and have a race. At the end of the race, you send the 4th and 5th place horses to the glue factory and return the top 3 to the paddock. After 10 races, you have eliminated 20 horses. The remaining 5 run the 11th race for the top 3 spots. As a lower bound, you cannot do it in fewer than 5 races because some horses would never have a chance to run. With exactly 5 races, if you divide the 25 horses into 5 heats to let every horse run, you still have no comparison between those heat races. Now, I have a interesting N < 11 that works, the problem is to PROVE that you cannot do it in M < N races.
2003-08-30, 23:49   #6
Gary Edstrom

Oct 2002

1000112 Posts
Re: Horse Race

Quote:
 Originally Posted by Gary Edstrom There are 25 horses which all run at different speeds. A faster horse always beats a slower horse. You can race 5 horses at a time. What is the minimum number of races needed to determine the three fastest horses in order from fastest to slowest? There are no ties and you may not time them.
I'm not going to post the correct answer just yet. However, I will give one very common wrong answer. Some people will say "6 races". Their logic being to run a first set of 5 races of 5 horses each, and to take the winners of those 5 races and run them in a final race. They will say that the fastest 3 horses are the first 3 horses in this second race. This is an incorrect answer, as I think most here will realize.

I will post the correct answer tomorrow (Sunday).

 2003-08-30, 23:55 #7 Fusion_power     Aug 2003 Snicker, AL 7·137 Posts I'll toss in a bit of my logic to see what others think. Run the first 5 races each with 5 horses. Drop the 2 slowest horses from each group of 5 because there are 3 horses that are definitely faster than them. This leaves 15 horses to run in the next races. The key is which horses race against each other in the next 3 races. Put the 5 fastest horses in one group to run against each other. Put the number 2 horses in another group of 5 and put the number 3 horses in a third group of five. Now run 3 races and from the group including the 5 fastest horses keep the top 3. I won't say any more because that would give the answer. Could it be 11? I don't think so. Fusion
 2003-08-31, 05:30 #8 c00ler   Jul 2003 52 Posts I need only 7 races
2003-08-31, 10:23   #9
Wacky

Jun 2003
The Texas Hill Country

21018 Posts

Quote:
 Originally Posted by c00ler I need only 7 races
But can you prove that it cannot be done in 6 ?

Gary has hinted that a proposed scheme for 6 races will not work.
But that is not the only 6 race scheme.

 2003-08-31, 13:04 #10 Fusion_power     Aug 2003 Snicker, AL 11101111112 Posts I'll propose a couple of scenarios. Run these numbers through your "method" and see if you arrive at the correct horse sequence. These numbers are randomized into a specific pattern that should cause failure of certain patterns. The only requirement is that you must run the first 5 "horses" as a group. In this example, that means 2, 6, 23, 24, and 25 would be the first group of five. Presume that the higher numbers correspond to the faster horses. 2, 6, 23, 24, 25, 1, 9, 12, 15, 19, 3, 7, 8, 11, 14, 4, 5, 10, 13, 22, 16, 17, 18, 20, 21. In this scenario, the first group should be 1, 2, 3, 4, and 5. 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25. For the record, I have found 3 solutions so far, the first is the basic solution in 11 races as mentioned by Wackerbarth. The second is a 9 race solution that I hinted about in a previous post. The third looks like it works in 7 races but I still have to check a few things out to make sure it is viable. Fusion
2003-08-31, 14:25   #11
Gary Edstrom

Oct 2002

3510 Posts

Quote:
 Originally Posted by c00ler I need only 7 races
7 races is correct. First, run 6 races exactly as described in my "wrong" solution above: Run 5 races of 5 horses each. Have the 5 winners of these races race in a 6th race. The winner of the 6th race is the fastest horse, so he doesn't need to race again. You only need to resolve 2nd &amp; 3rd place. The horces in this 7th race will be the 2nd &amp; 3rd place finishers in the 6th race, along with the 2nd &amp; 3rd place finishers from the first race won by the fastest horse in the 6th race plus the 2nd place finisher in the first race won by the 2nd place finisher in the 6th race. A little analysis will show that there are no other possible candidates for 2nd &amp; 3rd place. You now have 5 horses to run to resolve 2nd &amp; 3rd place in a 7th race.

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong jasong 0 2015-08-24 06:11 c10ck3r Puzzles 19 2013-03-27 14:00 davieddy Puzzles 13 2011-11-03 15:49 __HRB__ Soap Box 0 2009-03-14 06:15 graeme Puzzles 6 2008-09-12 16:47

All times are UTC. The time now is 10:28.

Wed Dec 1 10:28:58 UTC 2021 up 131 days, 4:57, 1 user, load averages: 1.00, 1.09, 1.13