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.

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.

I have an answer as well, and it seems too low to be improved upon.

[quote="tom11784"]I have an answer as well, and it seems too low to be improved upon.[/quote]

same here :surprised:

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.

Re: Horse Race
 

[quote="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.[/quote]

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).

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

I need only 7 races :banana:

[quote="c00ler"]I need only 7 races :banana:[/quote]

But can you prove that it cannot be done in 6 ?

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

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

[quote="c00ler"]I need only 7 races :banana:[/quote]

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.