25 Horses
Recently I stumbled across a problem which google has allegedly been posing to interviewees and thought I’d have a stab at it.
The problem.
There are 25 horses. You can race 5 of them against each other at a time and while you know the order they finish in for each race you don’t know how quickly the finished. The task is to find the 3 fastest horses and their order in the minimum number of races. Pretty simple, eh?
My gut instinct was:
· Race 5 sets of 5 and eliminate all the 4th & 5th positions as the top 3 of any race could be the top 3 overall, this leaves you with 15 horses.
· Then race 3 sets of 5 also eliminating the 4th & 5th positions leaving you with 9.
· Next race 5 against each other 1st & 2nd advance to the end. 4th & 5th are eliminated while 3rd is raced against the remaining 4 from which the top 3 advance leaving us with 5. The reason the 3rd horse races twice is that to end the round with 6 horses is clearly inefficient as it would need 2 more races to resolve. By racing the 3rd horse twice if it is the 3rd fastest horse overall it can still make the final by winning the 2nd race of the round while if it is not in the top 3 it will be eliminated. This approach also allows 3 horses to progress from the 2nd race in case all of the top 3 are in that race.
· Lastly race the remaining 5 horses, the top 3 from this race are the top 3 in order.
Taking 11 races, this is a fine solution, but it instinctively feels a little clunky. There’s some efficiency in the 3rd step but the fact that the 3rd fasted horse could run 5 times just feels awkward. Also the fasted horse has shown they’re fastest in their group 4 times, we can do better.
Learnings to carry forward.
1. The first 5 races are needed to set up the remaining races
2. The fastest horse should probably only run twice to be efficient.
3. The 3rd placed horses in the first round should probably also only run at most once more when determining our 3rd place.
2nd take:
· Race 5 sets of 5 and eliminate all the 4th & 5th positions this leaves you with 15 horses.
· Race all the winners from the first round. The winner here is the fastest
· Race the remaining 4 winners and the runner up from the winners original race. The winner here is 2nd fastest.
· Race the remaining 4 from the previous race and the runner up from the 2nd fastest original race (which could be the 3rd place if 1st & 2nd came from the same original race) the winner here is 3rd fastest.
Using only 8 races this is a significant improvement on the first solution and arrives at the ranking in a more staggered fashion. It still has room for improvement however with the 4th & 5th horses from the 6th race (the winners race) running 2 more times after we’ve determined they cannot sit in the front 3.
Final solution:
· As with the 2nd solution we race 5 sets of 5
· Also the same as the 2nd solution we will then race the winners with 1st from this race being the fastest.
· The 7th race is different, however. we’re going to need some notation at this point. We’re going to label all the horses with a letter & number. The letter corresponds to which of the original 5 races the horse was in with the number being their position in that race. The letters will be assigned based on the rank of their fastest horses ranking in the winners race. The horses from the A race were those in the same original race as the fastest horse which we will label A1 in this system. The top 3 can only be, A1:A2:A3, A1:A2:B1, A1:B1:B2, or A1:B1:C1 as we already know 3 horses faster than any other horse. With A1 already identified as the fastest the final race must be A2, A3, B1, B2, & C1. The winner of this race is 2nd fastest while the runner up is 3rd .
Using only 7 races this solution is very efficient, if not perfectly so. No horse races again after we know it’s not in the top 3 and only the 2nd horse is guaranteed to race 3 times. I like this question as a brain teaser. It requires the kind of iterative, combinatorial thinking that is needed in process & system engineers and as an interview question in either of these fields it probably fares well. However, I do fear that, if it is used outside of these fields, it might lead to the wrong decisions. This question is so focused on efficient processes, excluding all other considerations, that to use it outside of a systems context would be like measuring a fish for its ability to climb a tree.
