Out of 25 horses, pick the fastest 3 horses. In each race, only 5 horses can run at the same time. What is the minimum number of races required? 66 Answers6 races. After running 5 you have the 5 fastest horses out of 25. Run 1 more race of 5 horses to get the fastest 3. Show More Responses The above answer is not right. The correct answer is 8 races. Sid's answer is incorrect. The correct answer is 7 races. 7 races. We run five races with five horses. The five winners race in a sixth race while the 4th and fith place finishers are eliminated from further consideration. The sixth race show horse is faster than all the horses that participated in the preliminary races where the 4th and 5th place horses participated and they are eliminated from further consideration. The other horses in the preliminary race where the 6th race show horse participated are also eliminated. The show horse in the preliminary race where the 6th race place horse participated is eliminated since there are at least three remaining horses that are faster. We are left with 6 horses. We know the winner of the 6th race is fastest overall, so that leaves five horses to enter a 7th race for the overall place and show. Seems to me the correct answer is five. Assuming that each horse's performance is timed, by running five races with five horses each, you'll know the speed of all 25 horses. The three with the shortest times are the three fastest horses. Most responses assume you need multiple rounds, but these responses seem to assume that the five horses that finish first in the first round are the fastest five overall. That may not be the case. Just because a horse beat its four competitors doesn't mean it's one of the five fastest overall ... just that it was faster than the four it competed against. Consider: 5 races will ensure that each horse runs once. In race #1, the margin of victory could be so insignificant that the difference between horse #1 and horse #5 is.05 seconds (with 2nd place .02 behind, 3rd place .03 behind, 4th place .04 behind). The horse that finishes in 5th place in race #1 could actually be the 5th fastest horse of the 25. You wont know this of course until all 25 horses have raced. Horse #5 from race #1 could be faster than the first place finishers in all other 4 races. Rank the top 5 fastest times. Odds are that they were not all from the same race. Maybe you race them one more time against each other to verify your ranking technique (and in the good spirit of a playoff.) This brings the total to 6. 5 (or 6) is a great, pat answer if you know all of the particulars. Unfortunately, most programming in the world of finance wants to make sure nothing is being missed. The interviewer wants to see how you think and how you code. If you had a timer, yeah, 5 races are what you need. Sort all 25 horses by time and voila, you have 1, 2, and 3. However, horses (loans, retirement funds, Investments) will perform differently over time, distance, endurance, phase of the moon, etc. The interviewer wants to hear the deep answer to see your thought process. When you are dealing in operations that take milliseconds, extra loops in order to be thorough are not a bad thing. How about 11 races - 5 horses in Race 1. Best 3 face horses 6 & 7. Best 3 face horses 8 & 9. Best 3 face horses 10 & 11. Rinse and repeat. Or 12 races - first round - 5 races of 5. (W)in, (P)lace, and (S)how in each go to second round (15 horses). second round - 3 races of 5. W, P, & S in each go to third round (9 horses). third round - a race of 5 and a race of four. W, P, & S in each go to fourth round (6 horses). fourth round - race 1 - W, P, & S from round 3, race 1 and W & P from round 3, race 2 fourth round - race 2 - W, P, & S from round 4, race 1 and S from round 3, race 2 Not pretty, but definite. I think 5 is the correct answer. Why?: The first requirement is to get the minimum races (no tournament). Secondly, It does not dictate how to get the time. It only conditions 5 horses per race. Which mean 25 / 5 = 5 races. Now, How to time: the timer can help to get the individual hoese race time. These days the time can be measures upto 0.000 (there fractions) which is good enough. Aslo there is no condtion to handle exceptions, so we can skip any exception. 12 RACES ARE REQUIRED -------------------------------------- In the worst case scenario the 'best three' can be from a single team of 5 horses. So 5 races in round one. Chose all the first three of each of the 5 races. 3 races of all the 15 horses which were the 3 winners of the first round. Chose the 9 horses which were winners in round two and have 2 races for the 9 winners[ 5 & 4 horses] you get 6 winners. 1 race of 5 horses, out of the 6 round three winners, keeping one standby 1 race of 4 horses of round four winners with the standby. This will give you the best 3 horses out of 25 So you need to have 5+3+2+1+1 = 12 races in order to get the best three horses. Answer 12 races required. Sometimes the 2nd and/or 3rd best athlete do not get selected if they are teamed in a race along with the best athlete. dynamitemike's answer is the one. A timer could be considered but the problem would be pointless if you had a time. Run 5 races, let's say, Hij denoting the j-th rose in the i-th race, 1 <= i <= 5, 1 <= j <= 5. Eliminate the last two, since there will be three or more horses faster than them for sure. We are left with 15 horses. Run a 6th race with the Hi1 (the 1st placed horses). Suppose the results are Ha1, Hb1, Hc1, Hd1 and He1. The fastest horse in this race (Ha1) is the fastest horse of them all. The last two (Hd1 and He1) can also be eliminated because there will be three or more horses faster than them for sure (at least the top 3 of the 6th race). At this point, we have 12 horses to consider. But the 2nd and 3rd places horses in the preliminary races of the two worst placed horses (Hd1, He1) in the 6th races (Hd2, Hd3, He2, He3) can also be eliminated since there will be at least three horses faster than them. We have only 8 horses left. What about the 2nd and 3rd places horses in the preliminary race of the 3rd placed horse (Hc1) of the 6th race? There will be at least three horses faster than them (Ha1, Hb1 and Hc1). They can be eliminated. We have 6 horses left. Following the same reasoning, the 3rd placed horse in the preliminary race of the 2nd placed horse (Hb1) of the 6th race can be eliminated because there will be at least three horses faster (Ha1, Hb1 and Hb2). We have 5 horses left, namely Ha2, Ha3, Hb1, Hb2 and Hc1. These horses will run in the 7th race and the top 2 will join Ha1 and they are the top 3 horses among the 25 initial. Note that the maximum numbers of races required is MAX = 1 + (H - R)/(R - T), if you have H horses, if you can use R horses per race and if you want the top T horses among all H. For H = 25, R = 5 and T = 3, MAX = 11 races. You get to this result simply through successive races eliminating the last two (R - T) and adding the same number of horses until all of them have raced. It is an exhaustive "brute force" approach. If we were looking for the fastest horse and could only use 2 horses at a race, the problem would actually be: "what is the minimum number of comparisons required to find the maximum value of an unordered set of N values?" A brute force approach would require N - 1 comparisons. In addition, another problem variation: given N^2 horses, if you can use N horses per race, then you only need N+1 races to find the fastest horse. Show More Responses Do I have resource to metter the time of each horse in each race? Assuming I have it. So I need only 5 races. Assuming I don't have it, I need to understand I cannot eliminate the second and third horses, because they could be faster than the fisrt horse of another race. Assuming either I can have more than one race for each horse with the same performance, after the first five races I eliminate 10 horses. After the next 3 races, I eliminate more 6 horses. Now I have 8 races and 9 horses. For the next 2 races I eliminate more 3 horses (2 in the 1st and 1 in the 2nd). Now I have 10 races and 6 horses. In the 11th race with 5 horses I eliminate more 2 horses, having 11 races and 4 horses. In the last 12th race I find the better 3 horses in order. So, in my opinion I need 12 races to find the best 3 horses, assuming I don't have resource to metter each horse time in a race and assuming each horse run always the same lap time. dynamitemike & Isac Costa nailed it. Seven races are needed without using a timer. You can only eliminate two horses a race maximum. Fastest 3 out of 5. The goal is to eliminate 22 horses (25 down to 3). So 11 is the minimum number of races needed. You have to assume that it's possible each race to actually have the fastest three horses in the bunch. So eliminating more than two horses in any race means you are assuming something that may not be true. Another angle on this. Everyone gets the part about 5 races with 5 horses each. The key is to realize that it is possible that any of those 5 races could contain 0, 1, 2 or 3 of the best 3. The sixth race between the five heat winners can eliminate the two slowest ones. The seventh race is key. After six races, we already know who the fastest horse is, so you only need determine #2 and #3. The fastest horse rests and eats some oats. + Take 2nd and 3rd place finishers from the heat that was won by the fastest horse + Take 2nd place finisher from the heat won by the second fastest horse in the sixth race + Now race these three along with 2nd and 3rd place finishers from the second race and pick the two fastest horses to be #2 and #3. 1 race. You already have the 3 fastest. Win, place, show. No one said i couldn't rerun the same race. The answer has to be 12 For the reasons stated above, and the fact that horses do not race in a vacuum. They are influnced by the other horses in the race, things like drafting, setting the pace. There are frontrunners, and closers. A horse may only run fast enough to win. If they did run in a vacuum, 5 races and a stopwatch would be all you would need - I didn't see that a stopwatch was supplied in the question. None. The way the question is phrased, it doesn't even tell you what the requirement is. 6 is the answer. 1. Race 5 horses 2. Eliminate slowest 4 3. Add 4 horses, race again 4. Repeat steps 2 and 3 until all horses have competed, the winner of the 6th race is the fastest horse. This assumes that: a) the horses will performance identically in each race b) timing devices are not available Santosh K. Rao has the right idea and so the answer is 12. However, the only problem I have with his suggestion is that in the second last step, sitting out the one horse (because you can run only 5 at a time) will give it a competitive advantage as it has raced one less race than the winning 3 horses that it is about to compete against. But this aside, 12 is the right answer. If a timer is available then only 5 races. But if a timer is not available then 8 races. Divide the horses into 5 groups (Group A, B, C D and E). Races 1 to 5 are intra-group races. Race 6::: The fastest horse from each group runs this race. The winner of this race gets the gold medal. Race 7::: 4 horses from race 6 will remain the same. However, replace the winner of race 6 with the next-fastest horse in the same group as the winner of race 6 (we will have this information from the results of races 1-5). The winner of this race gets the silver medal. Race 8::: Same logic as race 7. Replace the winner of race 7 with the next fastest horse of the same group. The winner of this race gets the bronze medal. Show More Responses I thought the answer was 9... then I read Debarshi's post... 8 is the right number. Nice I believe Issc's answer is correct and I will make it more clear by drawing a simple diagram. Lets map out the 25 horses on a grid: 1 2 3 4 5 ------------ 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 Above is the grid, the 1-5th places for 5 races are listed as columns. The 6th race, which races the 1st place of each horse, is listed as a row at the very top. So now we have a ranking for each column. From here alone, we see that the fastest horse is in the top left corner: 1 Then, in addition, we will add the possible contenders for 2nd place: 1 2 1 Finally, we will add the contenders for 3rd place: 1 2 3 1 2 1 Every other number not in this triangle are not contenders for the top 3, and are thus eliminated. Knowing that the top left "1" is already the fastest, we put the other 5 horses into the 7th race to determine the 2nd and 3rd place. Hope this helps. Apparently I can't edit my post; I made a typo above, let me retype the wrong portion: From here alone, we see that the fastest horse is in the top left corner: 1 Then, in addition, we will add the possible contenders for 2nd place: 1 1 2 Finally, we will add the contenders for 3rd place: 1 1 1 2 2 3 Every other number not in this triangle are not contenders for the top 3, and are thus eliminated. Knowing that the top left "1" is already the fastest, we put the other 5 horses into the 7th race to determine the 2nd and 3rd place. Hope this helps. This question is about three things: (1) recognizing path dependence (performance is based on the environment) (2) evaluating your ability to reason critically (3) your ability to to question assumptions (do we have a stop watch? does it matter?) There is no "right" answer to this question, they want to see you come to the conclusion that the right answer depends on your assumptions and what you're trying to measure. If you have race times and assume path independence the answer is 5. If you have race times and assume the paths are not independent it's 8-ish. No race times + path independence is 11. Basically they're asking you how many scenarios you should use to price an exotic derivative, but putting it into a context where you can't fall back on "stock" answer(s). Definitely 7. Top 3 in each race (a,b,c,d,e) are in play after round 1, 15 horses. Five winners from round one race. This gives you the undisputed top horse (let's call this horse a1) and moving on to the next round are b1, c1 (2nd and 3rd place in race 6) and a2,a3,b2,b3,c2,c3 for a total of 9 horses. First overall is already confirmed so we only need to determine 2nd and 3rd places now, so our pool is 8. We then eliminate c2 and c3 because the best c1 could do is 3rd place. We also eliminate b3 since the best b2 can be is 3rd place. Now we have 6 horses remaining. Only the bottom 5 run in the last race and the top two placers fill out our top 3. All of this assumes these horses run the same speed each race, of course. If I have a way to time them, 5 races is the minimum. If I do not, then the answer is 7 races. We take the winner from each of the first 5 runs. The ones who place 4th & 5th in this race not only disqualifies them from being top 3, but also disqualifies everyone who ran with them in their first run. The 3rd place finisher in this race is the only possible placer from his first run. The second place finisher in this race is the possible second place overall and the one who took second in that race has the possibility of coming in third overall. The first place finisher from the scond run is first overall and does not need to race again, but the second and third place from that horse's first race might get 2nd & 3rd overall so they need to run again. After you figure who needs to run again, there are only 5 of them so only one race is needed to determine 2nd & 3rd place overall... these horses ar the second & third place from the first run with the first place overall winner. The horse who placed second in their second run and the horse who was second in THAT horse's first run, and the horse who placed third in the second run. Another way of putting it. Assume no timer: 1) 5 races: run all horses. We'll call the races heats A, B ,C, D, E (eliminate last 2 in each race) 2) 1 race: run all 5 of the 1st place horses (eliminate last 2) 3) 1 race: assume the fastest overall horse was from heat A (we'll cal it A1), the 2nd fastest was from heat B (we'll call it B1), and the 3rd fastest was from heat C (we'll call it C1). the only possible combinations of fastest horses is: -A1, B1, C1 -A1, B1, A2 -A1, B1, B2 -A1, A2, B1 -A1, A2, A3 Therefore A1 is the fastest horse. So you only need to race the remaining 5 horses. Conclusion: 7 races are necessary. Assuming we know the second and third place winners and not just the first place winners of the respective races, then 7 is the minimum amount of races required, as theparadox put it. If we only know the first place winners, then we need probably around 10. The correct answer has been posted. It's 11 races, and Mark's reasoning from Jan 11 is correct: In each race you can eliminate at most 2 horses. Can't beat logic! 12 is undoubtably the correct answer here. Just by following pure simple logic and mathematics. First you need to determine a model for the iteration: Take 1 heat of 5 horses. Suppose the top three finishers in this heat are the fastest three out of any of the other 4 heats (We're working with a total of 5 heats, each consisting of 5 horses). This 1st heat will yield the fastest three horses. The 4th horse does not matter, and never matters. Even if the 4th horse is faster than the 1st place finisher in the 2nd heat, you are still left with the top 3 horses in the 1st heat. The 4th place finisher is irrelevant in any heat. Now assume you have the slowest 5 horses in the 1st heat. Then no matter what, these horses will be weeded out in future heats against all the top three finishers of the other heats. So what we conclude here is that the top three horses in each heat are the only relevant horses considering the fact that we are looking for the fastest three horses. Once we know this, the problem is simply an iteration. Here it is: Run 5 races, select the top 3 of each heat. (We are left with 5 x 3 = 15 horses) Run 3 races, select the top 3 of each heat. (We are left with 3 x 3 = 9 horses) Run 2 races (one with 5 horses, one with 4 horses), select the top 3 of each heat. (We are left with 2 x 3 = 6 horses) Run 1 race, select the top 3 of this heat. One horse sat out during this race and must be tested against the top 3. (We are left with 4 horses) Run 1 race, select the top 3 of this heat. These are the 3 fastest horses. It took 12 races to determine this. Show More Responses Most of you are making this harder than it has to be. You run five races and time each horse once. You compare their individual times (regardless of who they raced against directly )and pick the top three. 7 is correct. if you label the horses 1-25 and create groups of 1-5, 5-10, etc for the first 5 races and for simplicity the horses finish in numerical sequence for each heat. So horse 1, 6, 11, 16, & 21 won their heats. Race the winners and they also finish sequencially so horse #1 wins and it gets the gold. That means horse 11 is best case 3rd fasted and 12-25 are eliminated. Now the 2nd fasted horse can only be #2 or #6. If it's #2 then the 3rd fasted can only be #3 or #6 so that eliminates #4 & #5. Howver, if #6 is the 2nd fastest then the 3rd fastest can only be #2, #7, or #11. This eliminates #8, #9, & #10. After the conceptional eliminations, we are left with #2, #3, #6, #7, #11 for the seventh race. The top 2 join #1 in the winner's circle. Answer is 11 as posted multiple times... no assumptions should be made (timer, won a heat then you're faster than others etc.) In this case, each race of 5 horses would eliminate 2 from contention as being top 3. In order to eliminate 22 horses (25 - top 3), you would need 11 races. the question is not fully defined! instantaneous velocity? over a long or short race? do we include a running start? on that day or on average during the horses' lives? on what planet? what surface? what weather? with or without drugs? with or without a rider? what weight rider? how experienced? saddled? bridled? etc, etc, etc........... 7 is the right answer. Guys, who suggests 11 and 12 - please, try to understand the explanation first. I tried, and I got it finally. let's assume horses 1, 2 and 3 are the fastest. But we don't know it. 1) first 5 races 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 let's assume horses 4, 5, 9, 10, 14, 15, 19, 20, 24 and 25 are the slowest. They are eliminated first. We established already that first three horses in each race stay, cause they could be the fastest of all. 2) 6th race - we take only the fastest horses from all races, let's assume these are 1 6 11 16 21 1st horse we will make the fastest. Let's put it in the pocket. Let's assume the horses came in the order the are standing. First 1, second 6, third 11, forth 16, fifth 21. 3) the 7th race is the key!!! It's the most complicated race to organize. let's see: in this race we don't take the horses number 1(we know it's the fastest of all), we don't take the horses 17, 18, 22 and 23 - they are slower than the slowest horses 16 and 21. Horses number 12 and 13 are slower than 11, and logically, than 6 and 1. The same with the horse number 8: we know already that it is slower than 6, 7, and 1. The only horses which can possibly be faster than the 6 and 11 - are the horses number 2, 3 and 7. So, the 7th race is between 2 3 6 7 11 the first two in this race - are the second and third fastest of all. Looks like I can add a new perspective, the answer is 6. This is based on the wording of the question where they ask for the minimum number of races required to find out. They don't ask for the minimum number guaranteed to find out. So.... you run one race, and then you run the third place finisher in that race in the next five races against 4 new horses in each race. If the original third place finisher wins the next 5 races you have your answer in the minimum number of races. I don't want to guess the odds of this very remote scenario taking place but it is the minimum. Of course the "outside the box" answers might be passable, I especially like, "None. If I already chose the fastest three horses, they are the fastest." But mathematically, it's 7, assuming the horses always run at the same speed. Natalya did probably the best job explaining it, but I'll try a different tack (ha!). I encourage you to write this down and cross out the eliminated horses. Assume the 25 horses are named A-Y. Race 1: A B C D E Race 2: F G H I J Race 3: K L M N O Race 4: P Q R S T Race 5: U V W X Y So far, yes, the people saying you can only eliminate 2 horses per race are correct. We've only eliminated the slowest two in each heat thus far. Assume the left-most was the fastest and the right-most was the slowest. Now we race the winners: Race 6: A F K P U Now we've added a significant amount of information. Not only can we eliminate P and U, but we eliminate all of the horses that they defeated. We can also eliminate all of the horses that K defeated, but we can't eliminate K itself. For each of those horses, at least A, F, and K are faster. Lastly, we can also eliminate H, because we know for a fact that at least A, F, and G are faster. We know A is the absolute fastest, so that leaves: Race 7: B C F G K The winner and runner up have to be the second and third fastest, respectively. Let's look at this question backwards how many horses can be eliminated in each heat. Heats 1-5 you eliminate all horses that did not finish in 1-3 place. Heat 6 you run top horse from heats 1-5. You can eliminate three horses from the 4th and 5th place horses heats, plus the 2nd and 3rd place horses in the heat 6 3rd place finishers original heat, plus the 3rd place finisher in the heat 6 2nd place finishers original heat. The 6th race eliminates 9 horses. This leaves the horse that finished 1st & 1st who is in for sure and the following 5 horses to race again in heat 7: The two remaining horses from the winner's first heat, the heat 6 2nd place finisher and the horse that finished second to him in their first heat and the third place finisher in heat 6. Top two are combined with the 1st 1st horse for the answer. The Right Answer is SEVEN!! Think of the question "How many people defeated a Horse?" After the first round (which everyone agrees is a round of 5 races of 5 horses each) we get the following matrix ---------------------------- AFTER FIVE RACES ---------------------------- 0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 Now when we play all the Winners of these races in one match (The First Row) interestingly these numbers change to the following. Note that if your team's Winner loses against one person (stands second) your entire team shifts one place down (The entire column's number increases by one). If your team member loses against 2 people then your entire team shifts down two places. (Increases by 2) ---------------------------- AFTER SIXTH RACE ---------------------------- 0 1 2 3 4 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8 Now if a horse has been defeated more than 3 or more times that clearly indicates that there are at least 3 horses better than it and hence you that particular horse is eliminated That leaves us with the following. 0 1 2 1 2 2 You now need only one more race to decide who is the second and third. You already have found your Ace Horse ;) I could like to choose 8 races. race 1: A B C D E race 2: F G H I J race 3: K L M N O race 4: P Q R S T race 5: U V W X Y This is much same as others to drop the last 2 horses in each race. Drop: D E I J N O S T X Y Pick the fastest horses on race 1 to 5 race 6: A F K P U After race 6 I could drop 8 horses, Drop: H M P Q R U V W Remaining: A B C F G K L As A is the fastest from race 6, I could states H and M won't be the top 3 horses and A is the fastest. Combination of top 3 should be (AFK), (ABC), (AFG), (AKL), (ABF) and (ABK). Thus, my race 7 is to test if C is the third fastest of the horses above. race7: C F G K L If C is the fastest then I am done. If not, drop C. race8: B F G K L DONE ~~~~ Show More Responses The answer is definitely 7. Read here for a very detailed and easy to understand explanation: http://www.programmerinterview.com/index.php/puzzles/25-horses-3-fastest-5-races-puzzle/ Hi. If all 3 fastest horses were in the same group for the initial race and the 2nd place horse from that group won race 7, the 3rd place horse could not be eliminated without racing. The answer is that 7 races are likely needed, but an 8th race might be needed. The chance of needing an 8th race is 3 and 1/3 percent. "daved18" You are the Winner!!!!!!! Using only the information given and nothing else you have correctly answered the question. That being said I really enjoyed reading all the other perspectives given. It really shows how many approaches there are to answering a question without being able to ask any. You need to make a determination of whether or not a horse's time is affected by the horses it races against. If not, the answer is of course 5. If so, then you can start looking at the other options listed above. 10 - The correct answer can only be 10. (Note: those who answered 12 are close, but they fail to conclude that, by racing the 3rd place horses together in separate heats, they can eliminate one unnecessary race.) By the way, the question asks for the fastest 3 horses – so we can assume nothing less than that the results must be exact. Some assumptions can be made: 1. The 3rd fastest horse in each race (other than those races of only 3rd place horses), could be the 3rd fastest overall , so it can never be fully eliminated. It is possible that it was forced to run all of its races against the fastest two horses. 2. The 3rd fastest horse in each race can never be the 1st or 2nd fastest horse, so you can eliminate all 3rd place horses by racing them together. Only the fastest of these 3rd place horses could ever be the third fastest overall - so in these races, only the fastest needs to be promoted. First heat (5 races – total = 5): Take the top 2 horses from each race and put them aside for the third heat (10 horses total). Second heat (1 race – total = 6): Race all 3rd place horses from the first heat. Only the fastest horse in this heat needs to be promoted. Third heat (2 races – total = 8) Race the 1st and 2nd place horses from the first heat. The top 3 horses from each race gets promoted (6 horses total). Fourth heat (1 race – total = 9) Race the two 3rd place horses from the third heat and the winner of the second heat (all 3rd place horses). The fastest of these horses could be the overall 3rd fastest, but it is the only one needs to get promoted. Fifth heat (1 race – total = 10) The two fastest horses from each race in the third heat, along with the winner of the fourth heat. Top three horses in this heat are the fastest three overall. Again, the answer is 10 – and it can only ever be 10. I made a mistake - the answer is 9. If you race the 2nd place horses from the first heat together (in the second heat), the winner of this race could ever be the 2nd or 3rd place overall if it raced against the 1st place horse in the first heat. But because only one of these 2nd place horses could have raved against the fastest horse overall, all others in this race could never be even 3rd place overall, since it would have lost its first heat to, at best, the 2nd place horse overall and then lost the second heat as well. I do apologize for not catching this in my first post. Again – the answer is 9. debarshi nailed it. 8 races. it also means that the general answer, where: n = number of horses r = maximum number in a race p = number of places needed is , in APL, p + ? n÷r 7 races is the correct answer I think 9 races will solve the problem... 1) 5 races to get locally top 5 horses 2) In race #6, I will race the 5 winners from 1st round. 3) In race #7, I'll race the 2nd place holders from round 1 with each other. 4) In race #8, I'll race the 3rd place holders from round 1 with each other. 5) Now, race the top 3 from race #6, with the best horse from race #7 and race #8 That's it ! The top 3 of this 9th race are your 3 fastest horses. Explanation: From first 6 races, you get the undisputed champion Assuming that you raced the actual 3 fastest horses together in one of the first 5 rounds, you give chance for the second fastest horse in race #7. Again, assuming the previous worst case scenario, you grant the third fastest horse race #8 And finally, you race the top 3 from race #6 with top 1 from race #7 and top 1 from race #8. If the ideal case turns out, where first 5 races gave you the actual fastest horses, they would naturally win the race #9 (since you kept the top 3 amongst them) So the answer is 0. No races are actually required to do as the question asks, which is to pick the 3 fastest horses. Had the question been asked to provide the minimum number of races to PROVE you have picked the 3 fastest horses then I believe the answer is what ever you overthinkers know the answer to be. Show More Responses Travis took my answer. Good answer by the way Travis. It is designed to see your thought process. Do you have a tendency to over think or over analyze a problem? First we need some assumptions. Let's say the horses perform the same in different races, and we are looking for the minimum number of race to determine the fastest three. 1) If we got a timer, the answer is five, obviously. 2) I we did not have a timer and could only record the standing of horses, the number is 7. Firstly, 5 races will cover all 25 horses and give us the champion of each group. 6th race is between the 1st horses of 5 groups, and we name the groups A, B, C, D, E, according to the standing of this 6th race. The 2nd and 3rd horses of group A, and 1st and 2nd horses of group B, also with the 1st horse in group C will attend the 7th race. The top two of 7th race and 1st horse of group A give us the fastest 3. See http://math.stackexchange.com/a/746801/6876 The answer is: You need 7 races. The answer is 7 races . http://www.programmerinterview.com/index.php/puzzles/25-horses-3-fastest-5-races-puzzle/ 8 races. 25/5 = 5. Winners = 5 * 3 = 15. Winers vs winners = 3 races + 5 = 8. I 7 check career cup book for explanation 5 races. you just need a stopwatch!? 7 races (see here: http://www.programmerinterview.com/index.php/puzzles/25-horses-3-fastest-5-races-puzzle/) Ans: 8 After 5 races you have 5 sorted lists. Now you have to merge them using a 5-way merge. First 5-way compare: race 6 Second 5-way compare: race 7 Third 5-way compare: race 8 5 races of 5 will yield 15 new candidates by picking the top three each time, 4 and 5 are eliminated 3 races of 5 will yield 9 new candidates by picking the top 3 each time, 4 and 5 are eliminated 2 more races, one of 5 and another with 4 will yield 6 new candidates by picking the top 3. 2 more races of 3 will yield 4 more candidate picking the top 2 one more race will yield the 3 top horses. 5 + 3 + 2 + 2 = 12 races will yield the absolute 3 best horses. Show More Responses 25 horses 5 groups of 5 horses choose the first place horse from each group have have them race From this race we gain information ---The 1st place can win in the other group, but the same does not go for the other top two horses. ---2nd place can beat the horses in 3rd place's group and the other groups, but it's uncertain if 2nd place can beat horses in 1st place's group ---it is uncertain that 3rd place can beat horses in 1st and 2nd place's groups, but can beat horses in the other groups 2 place races the horse in 1st places groups. whichever horse wins is able to beat horse in all the other groups except the original winner of the top 5 horses 3 place races horses in 2 place's group, whichever horse wins is able to beat horses 3 place's group and 2nd places group. --That same horse faces 1st places group in 1st place's group, whichever horse wins is able to beat horses in 1,2,3 places group but not the original 1st place horse. 9 races in total and you have the top 3 horses. 5 Races It says fastest horses, NOT the ones that win the race. In 5 races, you will know ALL of the horses time around the track. 1: ABCDE : Keep fastest horse out of race, ex. A time x secs 2: FGHIJ : Keep fastest horse out of race, ex. F time x secs 3: KLMNO : Keep fastest horse out of race, ex. K time x secs 4: PQRST : Keep fastest horse out of race, ex. P time x secs 5: UVWXY : Keep fastest horse out of race, ex. U time x secs Out of the 5 fastest horses, one winner from each race, pick the top 3 fastest horses out of A F K P U: ex. A K U 5 Races Showing my work... 5 Races: 1) ABCDE : Keep top 3 fastest lap times from ABCDE ex. ABC 2) FGHIJ : Keep top 3 fastest lap times from ABC FGHIJ ex. ABF 3) KLMNO : Keep top 3 fastest lap times from ABF KLMNO ex. AFK 4) PQRST : Keep top 3 fastest lap times from AFK PQRST ex. APQ 5) UVWXY : Keep top 3 fastest lap times from APQ UVWXY ex. APU The top 3 fastest horses would be APU |