# 25 Horses Puzzle - Find The Fastest In Minimum race || Google Interview Puzzles

Puzzle Details

There are 25 horses among which you need to find out the fastest 3 horses. You can conduct a race among at most 5 to find out their relative speed. At no point, you can find out the actual speed of the horse in a race. Find out how many races are required to get the top 3 horses.

Solution

Let the horses be numbered as H1, H2, H3, H4, H5, ..., H24, H25. Now First arrange 5 races among horses as :

Race 1: H1, H2, H3, H4, H5
(let's say that H1 comes first in the race then H2 then H3 then H4 and then H5 and similarly happens for the next races ...)
Race 2: H6, H7, H8, H9, H10
Race 3: H11, H12, H13, H14, H15
Race 4: H16, H17, H18, H19, H20
Race 5: H21, H22, H23, H24, H25

Now arrange the race between winners of all the above races as :

Race 6: H1, H6, H11, H16, H21
So, Now we have H1, H6, and H11 as the top 3 winners of Race 6. So, there are some points that can be noticed through race 6:

So, Now we have H1, H6, and H11 as the top 3 winners of Race 6. So, there are some points that can be noticed through race 6:

1) As H16 comes fourth in the race, so we can be sure that horses (H17, H18, H19, H20) cannot acquire top 3 positions rather they can be at any position from the fifth one to the last position. So, In our final race, we do not need to include H16, H17, H18, H19, and H20 as we are interested in only the top 3 fastest horses.

2) As H21 comes fifth in the race, we can be sure that horses (H22, H23, H24, H25) cannot acquire top 3 positions rather they can be at any position between the sixth one to the last position. So, In our final race, we do not need to include H21, H22, H23, H24, and H25 as we are interested in only the top 3 fastest horses.

3) As H11 comes third in the race, we can be sure that horses (H12, H13, H14, H15) cannot acquire top 3 positions rather they can be at any position from the fourth one to the last position. So, In our final race, only H11 will participate, and the rest of all (H12, H13, H14, and H15) need not participate as we are interested in only the top 3 fastest horses.

4) As H6 comes second in the race, we can be sure that only H7 could have the possibility of third fastest horse, and horses (H8, H9, H10) cannot acquire top 3 positions rather they can be in the any position between the fourth one to the last position. So, In our final race, only H6 and H7 will participate, and the rest of all (H8, H9, and H10) need not participate as we are interested in only the top 3 fastest horses.

5) As H1 wins race 1 and also wins the race with the winner of all rest of the races, so, till now we have found that H1 is the fastest horse among all. So, we do not need to race H1 again with any other horse.

6) As H1 comes first in the race, so we can be sure that only H2 and H3 could have the possibility of second and third fastest horse respectively and horses (H4, H5)cannot acquire top 3 positions rather they can be at any position between the fourth one to the last position. So, In our final race, only H4 and H5 will participate, and the rest of all (H8, H9, and H10) need not participate as we are interested in only the top 3 fastest horses. So, for our final race, we have H2, H3, H6, H7, and H11 as the competitors for second and third positions. So, we have,

Race 7: H2, H3, H6, H7, H11 Let's say H2 and H3 come at first and second position respectively. So, finally, we have the top 3 fastest horses in just 7 races among 25 horses as: H1 > H2 > H3