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 find out the fastest 3 horses by 5 races of 5 horse in each race.
• Only 5 horses can run in each race otherwise we could have find out fastest 3 horses by just one race of 25 horses.
  
  

First 5 Races

So at this point we are certain that we need minimum 5 races first

25 horses / 5 horses per race = 5 races

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

Where RxHy Where R is race, x is race number, H is horse, y is horse number

After first 5 races we will have a winner for each race. Result of first five races are as follows:-

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

6th Race (The Race of winners of first 5 races)

Now we need 6th race of all the winners of first 5 races i.e. R1H1, R2H1, R3H1, R4H4, R5H5. This race will reveal the fastest horse out of all 25 horses. Result of 6th race is as follows:-

For simplicity let’s assume first horse of first race i.e. R1H1 is winner for 6th race.

Now we know the fastest horse R1H1 out of all 25 horses but we don’t know the 2nd and 3rd fastest horse yet because 2nd and 3rd might be from 1st race since R1H1 from Race 1 is the fastest horse OR from the winners of all first five races.

7th Race (The Race of Chosen Five)

To understand this 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

• Race 1: Since fastest horse R1H1 is from Race 1, second R1H2 and third R1H3 winner of Race 1 can be 2nd and 3rd faster so eliminate Second Last and Slowest. Also eliminate the fastest horse because that can not be 2nd or 3rd fastest. We already know that.
• Race 2: Second winner of 6th race R2H1 is from Race 2 so it can be 2nd fastest horse. If it is 2nd fastest then second winner R2H2 can be 3rd fastest. Eliminate rest.
• Race 3: Third winner of 6th race R3H1 is from Race 3 so it can ve 3rd fastest horse. Eliminate rest.
• Race 4: Fourth winner of 6th race is from from Race 4. Since we have to find 2nd and 3rd fastest horse. Eliminate all.
• Race 5: Fifth winner of 6th race is from from Race 5. Since we have to find 2nd and 3rd fastest horse. Eliminate all.

Now that we’ve eliminated the all of the horses that can’t possibly be in the top three, what are we left with? The chosen 5 horses, let’s do the 7th race:-

The first and second winner of the 7th race will be the 2nd and 3rd fastest horse out of all 25 horses. So you need minimum 7 races to identify fastest 3 horses.

5 races (of all 25) + 6th race (winners of first 5 races) + 7th race (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.