25 horses puzzle is a very popular brain teaser and have been asked in many top interviews such as Google and Amazon.
The puzzle is this.
Given 25 horses, find the best 3 horses, with the minimum number of races.
Each race can have only 5 horses.
You don’t have a timer to time the races.
What is the minimum number of races required to find the best 3 horses?
Watch the video for the visual explanation and the detailed answer.
Divide the 25 horses in five groups, A, B, C, D and E.
Based on their ranks, label them in each group as A1, A2, A3, A4, A5. The fourth and the fifth in each group can not be in the top 3 among all 25. So, eliminate them.
Now hold a sixth race between the fastest horses of each group that is, A1, B1, C1, D1 and E1.
Say, the sequence now is C1,D1, A1, E1 and B1.
E1 and B1 can not be among the fastest 3. Since they were the fastest in their respective groups, no other horse in that group can be in the top 3.
Eliminate the rows E and B.
Since at best A1 can be the third fastest, A2 and A3 can not be in the top 3. Eliminate them.
Since at best D1 can be the second fastest, D2 can be at best third fastest, hence, eliminate D3.
We already know that C1 is the fastest.
Now hold a seventh race between the 5 horses that are left, C2, C3, D1, D2 and A1.
The first two of this race will be the the second and the third fastest.
So, you need a minimum of 7 races to find out the best 3 horses in the lot.
Can your friends solve it? Share it to find that!
Here is an extension of this puzzle. What if there are 36 horses and you can hold a race of six horses at a time. How many minimum number of races will you need?