Avinash Ranjan wrote at 2007-07-24 09:18:15
There are much lesser number of races in which we can determine the best 3 horses.
1) 5 races of 5 horses each - Find the top three(I,II,III) from each group.
2) 6th Race - Pick Fastest (I) horse from each group and run a race among these 5 fastest horses.
- This should give out the fastest horse.
3) 7th race - From step 2, pick the 2nd ranking horse from the group which had the fastest horse and the remaining fastest horses (I) which took part in the race as part of step 2.
Run a race among these, which should give out 2nd fastest horse.
4) 8th race - Pick the 3rd horse from the group which won the 2nd fastest place and run the race among remaining horses in step 3. This step should give the 3rd fastest horse.
mthussain wrote at 2007-09-06 08:57:46
Very interesting problem. well First race 5 sets of 5 horses. This eliminates 2 horses from each race i. e numbers 4 and 5 of each set (as stated above the fastest 3 in one set could possibly be the fastest 3 in all 25 horses)Now we have 15 horses. Now we have 5 sets of 3 horses each.
The 6th race will be between the fastest horses from the first 5 races.
The fastest horse in this race is the fastest of all 25.
Horses coming in 4th and 5th get there sets of 3 from the first 5 races eliminated i. e. 6 horses eliminated.
From the set of 3 of the horse coming in third number 2 and 3 are eliminated as they are slower than the 3rd fastest horse. 2 more eliminated.
From the set of 3 of the horse coming in second the number 3 horse is eliminated as it 3rd to the second fastest horse making him a possibility for only the 4th fastest horse in the pack.
Theerfore this race eliminates 10 horses.
Race 7 is the final race for 2nd and 3rd position.
JJ wrote at 2007-10-05 05:48:09
You are way-off, man! It should be 7 races.
Rohit Agarwal wrote at 2007-10-15 23:00:44
I think I have a better solution available.
Divide the set of 25 horses into 5 non-overlapping sets of 5 horses each. Have a race each for all the horses in each set. This makes it a total of 5 races, one for each set.
Now, have a race for the winners of each of the previous 5 races. This makes it a total of 6 races.
Observe the position of each horse in the 6th race and correspondingly number the sets. i.e. the set of the winner of 6th race will be said to be set no. 1 while the set of the loser of the 6th race will be said to be set no. 5.
Now, possible candidates for the first three positions exclude the followings:
1. Any horse from set 4 or set 5.
2. Any horse except the winner from set 3,.
3. Any horse except the winner and the 2nd position from set 2.
4. Any horse except the winner, 2nd position and 3rd position from set 1.
So now we have 6 candidates for top 3 positions. However, we know that the winner of set 1 is the fastest horse in the whole group of 25 sets.
So now we have 5 candidates for the second and third position. What better way to find out who's who than to have a race of these 5 horses. Race them and this will solve our problem in just 7 races.
prince wrote at 2007-10-25 06:04:25
divide the horses into 5 groups a,b,c,d,e number them as a1,a2,..,a5, b1..b5, c1..c5, d1..d5 and e1..e5. Conduct 5 races within the groups. Youve 15 winners (3 frm each race). a1,a2,a3,b1,b2,b3...,e1,e2,e3. Now conduct a sixth race among a1,b1,c1,d1,e1. Youve 3 winners say they are a1,b1,c1. Now you can eliminate all the d's and e's. since d1 and e1 isnt even in the top 3. You also eliminate b3,c2,c3 as they cannot be in the top 3 as there are already altleast 3 horses faster than them. After this elimination, you are left with a1,a2,a3,b1,b2,c1.
a1 is the fastest of them all. So conduct a 7th race among a2,a3,b1,b2,c1 to determine the next 2.
PiorraBear wrote at 2007-12-10 22:36:11
This can in fact be done in 6 races:
Race 0ne: Randomly Select 5 Horse, race the horses, and set aside the winning horse
Race Two: Do the same with 5 other(no repeats) horses.
After Five races you will be left with the five fastest horses. The winner of the sixth race is the fastest one of all.
siddu wrote at 2008-02-18 09:47:18
There is a problem in the solution (minimum of 7 races required)given by Bernard. the problem is explained in the below logic.
1) group 5 horses each thus total of 5 groups (5X5=25)
2) race each group and select the fastest in each.
3) race the selected 5, that came fastest in each
the problem is at point two
what if the second fastest of the second group (or any group fort hat matter)is faster than the faster of the third group (any other group ).
Govind wrote at 2008-04-15 16:24:42
look at this...
I think we can make it in 6 Races...
Make 5 groups, each of 5 and rase them (5 races completed), take winner of each group and race them again (6th race) and you cna find the TOP 3 from this race
steve wrote at 2008-04-23 02:26:39
we have an Einstein in the name of Govind...fastest three horses could be in the first race itself. but u will choose only the fastest of those three to race again...
hussain wrote at 2008-05-22 14:43:20
Both the above answers are wrong.
Race five horses at a time.so totally FIVE races.
You will get five fastest horses from this.
Now the SIXTH race among those five horses which won will decide the top three.
SO SIX RACES required
Suhel Jain wrote at 2008-06-19 18:21:12
Can be verified anywhere, Full confidence
Initially hold 5 races of 5 horses each.
The top 3 horses of each of the 5 races are picked up ( as ultimate top 3 have to be top 3 among the individual race)
RACE COUNT TILL NOW : 5
now 15 horses left or 3 sets of 5 each. (Randomly arranged)
Now hold 3 more races among all the 3 sets in total. and take out top 3 horses from each set.
RACE COUNT TILL NOW: 5+3 = 8
now 9 horses are left.
So, choose any 5 horses and have a race.
top 3 of the race are chosen again
RACE COUNT TILL NOW: 8+1=9
now total of 3 (race top 3) and 4 out of the remaining ones are left ie total 7 horses left
So, choose any 5 horses and have a race.
top 3 of the race are chosen again
RACE COUNT TILL NOW: 9+1=10
now total of 3(race top 3) and 2 out of the remaining ones are left ie total 5 horses left
Have a final race between the 5 and get the top 3 to be the 3 fastest riding horses.
TOTAL FINAL RACE COUNT:
So, 11 RACES required
AndyX wrote at 2008-06-21 22:34:38
7 races required if all horses will have the same timing from one race to another.
11 races required if we are talking about real horses, e.g. in every race each horse will finish with new result.
It just the matter of how you formulate the question.
Lizard450 wrote at 2008-10-29 19:23:57
its 7 races.
First lets cut down the field. have 5 races, race every horse. Now lets race those 5 winners. This gives us the first spot.
Now lets go over every possibility for 2nd and 3rd place
P1. the 2nd and 3rd place horses of the "winners race"
p2. the 2nd and 3rd place horses of the fastest horse's original race
p3. the 2nd place horse of the winner's race lets call him w2 and the 2nd place horse of w2's original race.
The 3 possibilities above have 5 possible actors, put those 5 actors in the final race and you will now now your 2nd and 3rd place finishers.
Mazen wrote at 2008-12-24 15:29:07
5 races are enough, but we need some "preparations".
Divide the distance into five equal lenghts. Race the first five horses. After they've reached the 1/5th of the distance, run the 2nd 5 horses. Proceed in this way until the last 5 horses. This way it will be easier to compare and quickly figure out the fastest 3 or 5 of all. (That will work of course if horses' speed is constant and, for strictly practical purposes, you should take a distance long "enough" so horses dont run into each other :))
mahatmakain wrote at 2010-02-18 23:38:08
So far, no one seems to have it right, including Bernard. In fact, I can very easily prove Bernard is wrong, with a grid.
* Set up a 5X5 grid, one box for each horse.
* Assign a random top speed to each box (horse).
* Label columns A-E, rows 1-5.
* Sort each column from fastest to slowest (these are the first 5 races).
* The fastest horses in each group are 1A, 1B, 1C, 1D, 1E.
* Race these horses (6th race) to find #1.
* Assume horse 1C is #1. Eliminate that horse from the head of column C and pop the others upward.
* Race 1A, 1B, 2C, 1D, 1E (7th race). The winner is #2 overall.
* Assume horse 2C won this race (column C is hot!). Now eliminate it and pop the remaining horses upward.
* 8th race: 1A, 1B, 3C, 1D, 1E. The winner here is #3 overall.
The grid leaves no doubt as to which methods work, and none of the others passes the grid test.
Art Patron wrote at 2010-04-01 23:21:53
mahatmakain is almost right. It can be done in 7 races. Follow the above example.
After 6 races, we know that E5 will never beat anyone. In fact, rows D and E can be eliminated completely. Likewise, none of the 4 and 5 horses can beat the others. We are left with 9 horses.
C2 will never beat C1, so we can get rid of C2, and of course, C3.
B3 will never beat B2, and we know B1 is faster than C1, so B3 is out. That leaves 6 horses.
We also know that A1 is The fastest, nobody can beat. So race the remaining 5 horses (A2, A3, B1, B2, C1) to find the 2nd and 3rd placers.
Dennis wrote at 2010-05-18 23:05:01
it looks like most people say it should be 7 races and in the 7th race 2nd and 3rd from the 6th race and then they add 3 more horses from the 1st round...
my question to all of you. if the last that was added to the race didn't run a second race what is the chance that the other two (2nd and 3rd from race 6) will actually win the race? you are assuming these horses are robots and don't have any lactic acid build up after the second race... so really did you find the fastest 3 "real" horses or did you find the fastest "robot/programmatic" horses.
if i was interviewing the person i would want to see if they are thinking about the real world when they are solving the problem. ;-)
so in the real world i would have 5 horses run a 7th race (2nd and 3rd from the first race of #1 from 6th race, 2nd and 3rd from the first race of #2 from 6th race and 2nd place from the first race of #3 from 6th race). take the top 3 from from 7th and then race them against #2 & #3 from 6th race. now they all have run equal amount of race.
of course then there is the issue of some fast horses not running fast after 2 races and then did you really find the fastest hours or the one that has the best endurance. ;-)
i am guessing none of you ran track or viewed olympics. :-)
Rajkumar wrote at 2010-09-03 06:43:23
1. First arrange 5 races between each of 5 horse set, and note down the time taken by each horse who are in first three plcaes(winner, runner up and second runner up)
2. compare the time of each sets (three places horses time) 15 horses time have to compare here,
find the top 3 horses from the fifteen if we can find top three from 15, we need not arrange another race.
3. if we found the five top speed (all the five took same time), then we need to arrange another race.
the minimum number of races is 5 we have to arrange other race based on the time taken by the horses
DC wrote at 2010-12-31 05:41:47
Run five races with five different horses each race. Time them. The 3 horses with the fastest times are the fastest horses. Five races total. Not complicated. The horses they race against are not relevant, only which are the fastest.
Pieter wrote at 2011-01-04 17:22:59
Ok, if you can time them it's easy enough :-D
But if you have no method of timing, it's 7 races. The way to look at things is to ELIMINATE horses. This means that once you're certain there are three horses faster then horse x, horse x won't be in the top 3 (makes sense, no :-p).
So, of course you make 5 races of 5 horses first. Let's label them race A->E. This eliminates 2 horses from each race, since the top 3 of the race is of course fastest. So we're left with horses A1->3 till E1->3.
Let's race horse A1->E1, so all the winners. Let's say that horse A finishes first, B second etc till E last. The conclusions from this are a bit more complicated. Besides A1 being the general winner, the following horses are excluded from further competition for places 2 and 3 :
- E1->E3 : A1,B1 and C1 are faster then all three (since they are faster than E1 and E1 is faster than E2 and E3).
- D1->D3 : same logic, A1,B1 and C1 are faster again.
- C2 and C3 : same logic once more, but of course C1 may stay
- B3 : A1, B1 and B2 are faster (C1 might not be !)
So, we are left with 5 horses : A2, A3,B1,B2,C1. Let those 5 race and say they finish in the given order. This eliminates B1,B2 and C1, leaving A1->3 to be the winners.
So, to sum up we have 7 races :
- 5 with random configuration -> 10 horses eliminated, 15 left
- 1 with 5 winners -> 1 winner and 9 eliminated (E,D,C2->3,B3) : 5 left
- 1 with 5 left -> 3 eliminated and 2 winners : we're there
Hope this explains it a bit, no need for more races and to determine the 3 best ones from the 'winners race' is a bad idea too (since in this example they were all in race A for instance).
Carlene wrote at 2011-01-07 16:37:50
First race the horses in groups of 5 (that will be 5 races)
For each race, note the finish time for each horse
Take the 5 horses with the fastest finish times (this may not necessarily be the winners of each set)
Then race the fastest 5 then you get the 3 fastest
Nathan wrote at 2011-01-07 19:16:36
It can be done in 5 races.
Race each group of 5 horses.
The three fastest times win first, second, and third.
LifeAsGIJoe wrote at 2011-01-07 21:22:19
Only five races are required. Use digital clocks and a high-speed camera. Note the time to multiple positions past the decimal point that each horse crosses the finish line. The three with the fastest times of the 25 horses are the three fastest horses.
C4 wrote at 2011-01-07 21:52:58
If you time them.
This question is about thinking outside the box.
At race tracks they usually give every horses time.
golferbob wrote at 2011-01-07 22:27:35
guys....all your solutions are incorrect...you have to have all the horses run againist the fasted each race for 16 races.
race 1; 1 2 3 4 5
race 2; Winner of race 1, second place, third place, now add horse 6 and 7.
race 3..winner of race 2, second place , third place , now add the 8 and 9th horse
etc...until all 25 horses have run against the win place show of the previous race
Bubba wrote at 2011-01-08 00:29:25
5 races is all you would need if they are timed races. Simply take the three fastest time of all five races.
Math Teacher 2010 wrote at 2011-01-08 08:22:44
Pieter is 100% correct. I had my students "proof" this with poker chips and a grid. No matter how the numbered chips, AKA: horse's individual ranking were placed on the grid, it can ALWAYS be solved in 7 races.
Given the rules: all horse run same speed each race, no timeclocks are available.
Jeffy wrote at 2011-01-08 12:51:05
If you are looking for the minimum you can do it in 7 races.
First 5 races to find the top 3 in each race (1,2,3 A-E)
Race 6 determines the fastest, say 1A, and eliminates the 2 slowest, say 1D and 1E, that means that they are slower than the other 3 that raced and can't make it into the top 3, it also eliminates 3B, 2C and 3C since 3B was slower than 1B and 2B it cannot be in the top 3, same for 2C and 3C
Race 7 you can take the two that came in second and third, 1B and 1C, and race them against the three horses that haven't been eliminated yet, 2A 3A and 2B, then you take the top two of those and you have your fastest 3 horses.
Tony wrote at 2011-01-11 00:57:37
Five Races - each horse runs once
Use a stopwatch. Those with the fastest three times are the fastest three horses. (Obviously this does not allow for the variable of the degree to which a competitive environment impacts upon performance)
Hitesh Mangla wrote at 2011-01-12 12:08:40
I think its upto the way they are judged..
For example if there is no time keep and each horse should be defeated by at least three better horses..
then 11 races r required as Suhel Jain described..
If you are allowed to keep time.. then 5 races..
gpo wrote at 2011-01-17 13:08:51
Yes, 7 races is the correct answer.
MathTeacher correctly state the rules that are implicit (no timers, same rates each time a horse races). Otherwise you could, obviously, assume all of the timekeeping device known to man and do it in 5 races.
ArtPatron has the most succinct description of the process of elimination and Pieter's is also easy to follow and correct.
au4all wrote at 2011-01-22 23:49:48
> MathTeacher correctly state the rules that are implicit
1. Those rules aren't implicit.
2. Those rules aren't sufficient. For example, they don't include what to do in case of ties.
And they definitely don't math real life. There's no transitive rule in sports, and your system has never been used to pick the winner of anything. It's a curiosity, nothing more, far from implicit.
tschul wrote at 2011-02-10 16:40:33
>>First 5 races to find the top 3 in each race (1,2,3 A-E)
I do not get this statement. In the case that in group A are the fastest 5 horses, you'd eliminate A4 and A5 -> horse ranked 4 and 5. The only thing you can eliminate after the first 5 races and one race of the winners is the 4 horses in the group which finished last and the last 3 horses of the group before the last.
So, I come to 10 races in total:
1.) 5 - non overlapping groups
2) 1 - winners race
2a.) the winner of the winners is out, definitely fastest, the last 4 in the last group are out, the last 3 in the second last group
3.) take the second horse of the winning group, race again with all winners
GOTO STEP 2.) until 5 best horses are chosen.
Vijay wrote at 2011-05-13 18:34:03
Answer is 7 races.
let the GROUPS be A-E.
5 Races ( 1)A GROUP 2)B GROUP 3)C GROUP 4)D GROUP 5)E GROUP )
6th Race A1,B2,C3,D1,E2. You will get the top 3 horses.
For Example if the finish in the order of B2,E2,C3,D1,A1.
7Th Race for B1,B2,E1,C1,C2 TO Determine the top 3.
Apply any combination to the 6th Race and you will need only 1 more Race to determine the top 3.
Deep wrote at 2011-05-26 08:45:36
I found the best answer with a detailed explanation here (the answer is definitely 7 by the way - you can read below for more info):http://www.programmerinterview.com/index.php/puzzles/25-horses-3-fastest-5-races
tangerine wrote at 2011-05-29 17:21:18
All solutions that ignore the fact that the three fastest horses could randomly end up in the first group of five are wrong.
Races 1-5: Run five groups of five. Eliminate the LAST two horses in each of those race. You are down to 15 horses- 3 from each heat.
Race 6: After you run the first five races, race the five winners. the remaining horses that raced against the slowest two in race 6 are out. You have now eliminated an additional 6 horses - the two slowest from race two and the remaining 4 horses (2 each)that raced against them. You have 9 horses left.
Race 7: You have left 3 horses who won their heats and 3 who came in second and 3 who came in third. The only possible "winners" are the two that came in second and third against the winner of race six and the one that came in second against the second place horse in race 6. We know that the winner of Race 6 is in, so we race those who came in second and third in race six against the three possibles mentioned above. The top two then join the winner of race 6 as the fastest three.
Race 7, pick
Ennio wrote at 2011-07-27 07:21:56
I think the quickest and easiest way to pick the 3 top horses is as follows.
Race all 25 horses on 1 track and pick the top 3
TripleCrown wrote at 2011-09-12 14:26:38
I can't believe how overcomplicated everyone makes this. I'm with you Ennio! Put all 25 on one track, let them compete against everyone equally at one time, and find the first 3 over the finish line in a single race. Just because it says there are 5 tracks doesn't mean you have to use all 5!
Paul S wrote at 2011-12-08 09:47:22
I believe 7 races is the minimum number of races, without a stopwatch.
NUMBER: finish rank [1=fastest, 5=slowest]
LETTER: defines the race [A1=fastest in A, A5=slowest in A]
(###): speed , only used 3, fill in the rest as you please
Races1-5 [Race 5 horses in A against each other, then B and C]
****Sort them [1=fastest 5=slowest]****
Race 6 [Race A1-B1-C1-D1-E1]
Result: A1-B1-C1 -> A1 is the fastest horse over all.
Rearrange (if needed): A1=fastest horse group E1=slowest horse group. A1=fastest horse in A and E1=fastest horse in E
in other works A1>A2>A3>A4>A5 AND A1>B1>C1>D1>E1, But A2 is not have to be faster than B1
Eliminations: A1 is removed as its the winner overall.
Group D and E can we removed since their fastest horse came in 4th and 5th
C1 came in 3rd, so there is no way C2 to C5 can be in 3rd rank or higher overall
B1 came in 2nd, so B2 at best would be in 3rd, with B3-B5 eliminated.
Since there are only two more spots left A4 and A5 have no way of being 3rd.
Race 7 [Race A2-A3-B1-B2-C1]
Result: A2 first (second overall) A3 second (third overall)
Summary: A1-A2-A3 winners in 7 races.
After 5 races, re-race only the top 5.
This will not work as we have seen since A2 was the nd fastest overall and would have been eliminated
Karsh wrote at 2012-06-21 03:12:54
Think outside the box. 5 Races are required.
You race all 25 horses, in groups of 5. Track the fastest time, and then you can have your answer, the horses with the fastest three times are the top 3.
Mike wrote at 2012-12-10 19:21:25
This is a simplified non-statistical answer. The minimum number of races required is 5 races.
Start with 5 races (5 horses per race) set against the clock - as in the Olympic Games.
Select the top 3 fastest times. Done in 5 races.