25 Horses 5 Tracks Problem (Solved)

The 25 Horses 5 Tracks Problem is a famous Google interview question that has been asked in many companies to evaluate candidate’s analytical ability and problem solving approach.

Problem Statement

You have 25 horses
🐎🐎🐎🐎🐎
🐎🐎🐎🐎🐎
🐎🐎🐎🐎🐎
🐎🐎🐎🐎🐎
🐎🐎🐎🐎🐎

and you need to identify the fastest 3 horses 🐎🐎🐎 out of those 25. Only 5 horses can run in each race at the same time as there are only 5 tracks.

What is the minimum number of races required to identify the fastest 3 horses without using a stopwatch or timer?

Solution

This is an interesting puzzle. Let’s look at the limitations first.

• We don’t have a stopwatch or timer so we can’t record the finish time of each horse otherwise we could have found out the fastest 3 horses by 5 races of 5 horses in each race.
• Only 5 horses can run in each race otherwise we could have found out the fastest 3 horses by just one race of 25 horses.
  
  

First 5 Races

So at this point, we are certain that we need a minimum of 5 races.

25 horses / 5 horses per race = 5 races

Visualization is very important for such puzzles. Draw a matrix of horses for the first 5 races.

Where R is the Race and H is the Horse, 🐎R1H5 is the fifth horse of Race-1.

Results of first 5 races

After the first 5 races, we have a winner for each race:-

For simplicity let’s assume that the first horse of each race is a winner i.e. 🐎R1H1, 🐎R2H1, 🐎R3H1, 🐎R4H4, 🐎R5H5.

Race-6 (Race of winners of first 5 races)

We have 5 winners and the fastest horse will be in one of them.

Let’s make a 6th race of all the winners of the first 5 races i.e. 🐎R1H1, 🐎R2H1, 🐎R3H1, 🐎R4H4, 🐎R5H5.

Result of Race-6

We got the fastest horse after the 6th race:-

For simplicity let’s assume that 🐎R1H1 is the winner of the 6th race.

Now we know that 🐎R1H1 is the fastest horse out of all 25 horses but we don’t know the 2nd and 3rd fastest horse yet. They could be from the Race-1 because the fastest horse belongs that race or from the winners of the first 5 races? Let’s find out.

Race-7 (Race of the Chosen Five)

To find the 2nd and 3rd fastest horse, we need to align all the horses as per their ranking in each race and eliminate the horses which are definitely cannot be 2nd and 3rd fastest.

Let’s think and eliminate:-

• The first winner of Race-6 is from Race-1 i.e. 🐎R1H1. If it is the fastest horse then the next 2 horses 🐎🐎 in the Race-1 can be the 2nd and 3rd fastest i.e.🐎R1H2 and 🐎R1H3. Eliminate rest. Eliminate the fastest horse 🐎R1H1 as well since we are looking for 2nd and 3rd fastest.
• The second winner of Race-6 is from Race-2 i.e. 🐎R2H1 so it can be the 2nd fastest horse. If it is the 2nd fastest then the next horse in the Race-2 🐎R2H2 can be 3rd fastest. Eliminate rest.
• The third winner of Race-6 is from Race-3 i.e. 🐎R3H1** so it can be the 3rd fastest horse. Eliminate rest.
• The fourth winner of Race-6 is from Race-4. Since we have to find the 2nd and 3rd fastest horse. Eliminate all.
• The fifth winner of Race-6 is from Race-5. Since we have to find the 2nd and 3rd fastest horse. Eliminate all.

Now that we’ve eliminated all of the horses that can’t possibly be the 2nd or 3rd, we are left with the chosen 5 horses, let’s do the 7th race of 🐎R1H3, 🐎R1H2, 🐎R2H2, 🐎R2H1, and 🐎R3H1

Final Result

The 1st and 2nd winners of the 7th race will be the 2nd and 3rd fastest horses out of all 25 horses. So you need a minimum of 7 Races to identify the fastest 3 horses.

5 races (of all 25) + Race-6 (winners of first 5 races) + Race-7 (the chosen five) = 7 races

Conclusion

I have tried to explain the solution as easy as possible. Please let me know by writing in comment section if you still find it difficult to understand.