Hey, this is Presh Talwalkar
There are 25 horses
What is the minimum number of races needed so you can identify the fastest three horses?
You can race up to five horses at a time, but you do not have a watch
This problem is sometimes asked as a technical interview question at companies like Google
But since it is a little bit vague, let me present another version which has some details that allow you to solve the problem
There are 25 mechanical horses and a single race track
Each horse completes the track in a pre-programmed time and the horses all had different finishing times, unknown to you
You can race up to five horses at a time
After a race is over you get a printout with the order the horses finished, but not the finishing times of the horses
What is the minimum number of races you need to identify the fastest three of all the horses?
I was suggest to this problem by email from the puzzle maker Terry Stickels
And it is sometimes asked as an interview question at companies like Google
So can you figure it out?
Pause the video right now and give it a try
When you're ready keep watching the video for a solution
The answer is you can find the three fastest horses in a minimum of seven races
I will first describe the procedure in words, and then I will go over the solution in detail. So that you understand why it works
The first step is to divide the 25 horses into groups of five and race the horses in each group
This will be a set of five races
Next, take the winner from each group and race those five horses
The winner of this race, which is the winner of the winners is the fastest horse overall
Now in order to get the second and third fastest horses, we're going to have to do one more race
But to describe that race I'm going to have to present some notation
So label the five groups from step one as A, B, C, D, and E
to correspond to the groups for the horses that finished in
first, second, third, fourth, and fifth place for the race in step two
In other words, label the groups in Step one
according to the results of the winners race in step two
Furthermore, write a subscript to identify the order that the horse finished within a group
So A2 means the horse that finished second place in group A
So here's that final race. We do one more race with A2, A3, B1, B2, and C1
that is race the second and third fastest horses from group A
The fastest and second fastest horses from Group B. And the fastest horse from Group C
The top two finishers in this race will be the second and third fastest horses overall
So now I'm going to show you this procedure in detail and explain why it is the correct procedure
So we start up by dividing the 25 horses into groups of five
In this race we have a race of five horses and I'm going
to illustrate it so that the slowest horse is on the left and the fastest horse is on the right
I'll rearrange the horses if necessary
so that it follows that the slowest horse is on the left and the fastest horse is on the right
I'll do this for all the horses in all of the different groups
Now, we are going to take the winner from each group and race those five horses
This will be the horse on the far right hand side of each group
The winner of this race, which will be the winner of the winners, will then be the fastest horse overall
I am again going to draw this so that the
slowest of the winners is on the bottom and the fastest of the winners is on the top
We'll rearrange the groups as necessary to make this diagram work
So now we have the fastest of the winners
This will be the fastest horse overall
We know that it's beat every other horse within this group,
and it's beat the fastest horse in every other group
So we have identified the fastest horse overall
Now in order to get to the second and third fastest horses,
We'll have to identify the different groups
so we've the fastest group being A and the slowest group being E
So how are we going to get the second and third fastest overall?
We're going to do this by process of elimination
We can eliminate any horse that is slower than at least three other horses
If a horse is slower than at least three other horses
There's no way it could be the second or third fastest overall
So to start out with, we can eliminate all the horses in group E
Every single horse in this group will be slower than the fastest horses in groups A, B, and C
This is because the fastest horse was slower than the fastest horses in these groups A, B, and C
So all of the horses in groups, in group E, cannot possibly be the second or third fastest overall
For exactly the same reason we can eliminate all horses in group D
All of them are slower than A1, B1, and C1
We can continue this logic, and we can eliminate all the horses in Group C, except for the fastest horse
All of these other horses will be slower than A1, B1, and C1
Now in Group B, we can eliminate all the horses except for the two fastest horses B1 and B2
All of them will again be slower than A1, B1, and then B2
So the horses in third, fourth, and fifth place in Group B can be eliminated
From group A, we can eliminate the 5th and 4th fastest horses
because they will be slower than the top 3 horses within their own group
We're left with 6 horses. We can only race five at a time, but we can actually get rid of one of these horses
We've already identified the fastest horse overall, A1, so we don't need to race it anymore
We already know it's the fastest overall we can't learn any more information by racing it
So we can actually remove this horse from our race
So we now have A2, A3, B1, B2 ,and C1
and we do not know the relative speeds of these different horses
So we can do one more race with these five horses
The winner of this race will be the second fastest horse overall
and the runner-up will then be the third fastest overall
So these will be 7 races which will allow us to identify the three fastest horses
Now just a quick note. We've shown that 7 races is sufficient. I just want to explain why it's minimal
We obviously have to race each of the 25 horses once
And since we can race 5 horses at a time
that means we're going to at least start out with 25 over 5, which is 5 races
We're then going to need to compare the winners, which will be one more race,
And we're then going to have to compare at least the second place from group A
to the fastest horse in Group B
amongst other possible comparisons in order to find out the second fastest horse
So we know at least seven races will be needed and we've shown seven races is sufficient
Therefore the described procedure is optimal
Did you figure this out?
Thanks for watching this video please subscribe to my channel
I make videos on math and game theory
You can catch from my blog "Mind Your Decisions" that you can follow on Facebook
Google+ and Patreon you can catch me on social Media at Presh Talwalkar and if you like this video
please check out my books. There are links in the video description