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
