Skip to content Introduction
“Find 3rd fast horse in the minimum number of races” is an interesting puzzle that challenges both strategy and intuition. The quest to determine the third swiftest equine athlete amid a group demands a meticulous approach, balancing speed, precision, and shrewd tactics. Racing against the constraints of minimizing the number of contests while unraveling the hierarchy of equine agility presents an intriguing puzzle. Amidst the thundering hooves and calculated decisions, this endeavor embodies the essence of strategic thinking and mathematical deduction, engaging enthusiasts in a thrilling quest to pinpoint the third speediest horse within the least number of races.
Prerequisites
- Please learn about solving puzzles in a coding interview
Question
There are 25 horses and 5 race tracks. So 5 horses can be raced simultaneously. Find the minimum number of races to get 3 fast horses or 3rd fast horses.
Please find the full description of the problem from here
Brute-force solution to find 3rd fast horse
Clearly, all horses need to run once at least for that we need 5 races(5 horses per race since we have 5 tracks), let us call this round 1.
For round 2, take fast 3 horses from each race again. Total 3*5 = 15 horses so we need 3 races for 2nd round.
For round 3, Again pick 3 horses from each round so total = 3*3 = 9 horses.
In 4th round, we need 2 races to run 9 horses. Pick the top 3 horses from both rounds so we have 6 horses for the next round.
In round 5, Pick any 5 horses and race them. Pick the top 3 horses from this race and the 1 horse that didn’t participate last time, total = 4, race them again and pick the 3rd winner.
Total = 5 + 3 + 2 + 1 + 1 = 12 race.
Please understand with below diagram.
Optimal solution to find 3rd fast horse
Let us pause for a second and think about this solution. If we pay attention we will find that some horses are being raced unnecessarily twice, thrice, and more.
First of all first round is still needed because we need to run the horses at least once so 5 races from the first round are needed. Let us focus on the second round, 3 races are needed to race 15 horses. Since we already know the winner from each race so we should race the winners first because if any winner comes 4 or 5 then this horse or any horse whose position was behind in the previous race will be disqualified for the next round and we don’t need to race them unnecessarily.
By applying the same logic, the horse who came 3rd will be qualified for the next round but not the horses who came behind this in the last race. By extending the same logic the horse which came second and its follower will only be qualified for the next round. So the horse which came first and the two horses which 2nd and 3rd in the last round will only be eligible for the next round. Understand this with the below image
For next round we have only 5 contenders = 2 + 3(in 2 green boxes above) (excluding the winner from 6th race)
Let us race them together and pick the 2nd fast from this round. this will be the 3rd fast horse
So answer is 5 + 1 + 1 = 7 races in total
Let me know if you like this approach so that I can write more about such puzzles.
Conclusion
To solve any puzzle question we need to figure out all the details hidden inside this. In the context of the current question “Find 3rd fast horse” we did this systematically. Then we came up with a simple solution. Then we figured out all the redundant operations in this solution. This leads us to find the optimal solution without any such redundant operation and finally arrive at the best optimal solution.
We can apply the above approach to any puzzle and solve it elegantly.
Let me know if you need more such puzzles. Your valuable feedback and comments will be highly welcomed.
