mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2003-08-30, 13:15   #1
Gary Edstrom
 
Oct 2002

5×7 Posts
Default 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.
Gary Edstrom is offline   Reply With Quote
Old 2003-08-30, 13:49   #2
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

7·137 Posts
Default

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.
Fusion_power is offline   Reply With Quote
Old 2003-08-30, 17:28   #3
tom11784
 
tom11784's Avatar
 
Aug 2003
Upstate NY, USA

14616 Posts
Default

I have an answer as well, and it seems too low to be improved upon.
tom11784 is offline   Reply With Quote
Old 2003-08-30, 17:37   #4
axn
 
axn's Avatar
 
Jun 2003

3×11×157 Posts
Default

Quote:
Originally Posted by tom11784
I have an answer as well, and it seems too low to be improved upon.
same here
axn is offline   Reply With Quote
Old 2003-08-30, 19:41   #5
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

21018 Posts
Default

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.
Wacky is offline   Reply With Quote
Old 2003-08-30, 23:49   #6
Gary Edstrom
 
Oct 2002

1000112 Posts
Default 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).
Gary Edstrom is offline   Reply With Quote
Old 2003-08-30, 23:55   #7
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

7·137 Posts
Default

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
Fusion_power is offline   Reply With Quote
Old 2003-08-31, 05:30   #8
c00ler
 
Jul 2003

52 Posts
Default

I need only 7 races
c00ler is offline   Reply With Quote
Old 2003-08-31, 10:23   #9
Wacky
 
Wacky's Avatar
 
Jun 2003
The Texas Hill Country

21018 Posts
Default

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.
Wacky is offline   Reply With Quote
Old 2003-08-31, 13:04   #10
Fusion_power
 
Fusion_power's Avatar
 
Aug 2003
Snicker, AL

11101111112 Posts
Default

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
Fusion_power is offline   Reply With Quote
Old 2003-08-31, 14:25   #11
Gary Edstrom
 
Oct 2002

3510 Posts
Default

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 & 3rd place. The horces in this 7th race will be the 2nd & 3rd place finishers in the 6th race, along with the 2nd & 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 & 3rd place. You now have 5 horses to run to resolve 2nd & 3rd place in a 7th race.
Gary Edstrom is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
The human race, magnifier of the improbable jasong jasong 0 2015-08-24 06:11
Price is Right Race Game c10ck3r Puzzles 19 2013-03-27 14:00
Boat race davieddy Puzzles 13 2011-11-03 15:49
grass-mud horse vs. river crab __HRB__ Soap Box 0 2009-03-14 06:15
Horse puzzle 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.