Run 'em
A friend gave me this casually during our lunch today. Turned out to be a good puzzle. The puzzle is simple:
There are 25 men, you are required to find the 1st, 2nd 3rd fastest among them. There is a track where you can race them, 5 at a time. You are not allowed to time them and they all run at different speeds. Question is what is the minimum number of races you'd require?
There are 25 men, you are required to find the 1st, 2nd 3rd fastest among them. There is a track where you can race them, 5 at a time. You are not allowed to time them and they all run at different speeds. Question is what is the minimum number of races you'd require?

12 Comments:
My answer is 11. There are 2 ways you can complete this in 11 races:
1. Split 25 men into 5 groups (A,B, C, D, E) and race them separately. Pick the 1st, 2nd and 3rd of group A and race them with top three from other groups eliminating the 4th and the 5th in each race. This will take 6 races since there are 12 top men from B,C,D and E. Totally it takes 11 races.
2. Randomly pick 5 men and race them. Take then top 3 men and race them with rest (2 people coming in at a time) and eliminate bottom 2 at every race. This will also take 11 races since, after the first race, there will be 20 men and 10 more races (2 coming in at a time).
My answer is 11. There are 2 ways you can complete this in 11hings........
11 ?
Take 5.
Find the best 3. One race.
for remining 20 people,
take next 2.
combine with best 3 to form 5.
race them.
find best 3.
end for.
Total 1 + 10 (in the loop) = 11.
-Guhan
Ashok, Guhan,
11 was the first answer I came up with too.
But there is better. Think guys.
4 ?
Take 10. 5 at each side of the race track end. Race them so that they run towards each other (opposite end) at the same time. Find the best 5. You don't measure time here instead distance to find the best 5.
Take next 10. Repeat the same.
-Guhan
Now we have 10 best and 5 not yet raced. Among the 10 best find the best 5 again using the same method.
This best 5 can be raced against the not yet raced 5. Find the best 3 in this.
here is a clue....
You could do it in as less as 8 races.
Devide the men into 5 groups. Race the 5 groups, choose the toppers in each and run them in a 6th race. You'll now know the fastest among the 25. We still need to find the 2nd and the third. The 2nd has to either be one among the other 4 runners in the 6th race or the 2nd fastest runner in the group to which the fastest guy belonged. So take those 4 + 2nd fastest in the group to which the topper belongs and run them in a 7th race. The winner of this race is the 2nd fastest guy. 7 races done. We still need to know the third fastest guy. We repeat the same thing. i.e., from the 7th races' toppers' group, pick the next fastest guy and race him with the 2nd and 3rd in the 7th race. The topper of this 8th race becomes the 3rd fastest.
But keep thinking... the right answer is 7!
Guhan,
Strange how people think alike, the next resort after the 11 races often is for people to think up things like this.
Nope. 5 is a race. To determine the fastest you need to run and let them complete on the track.
if you run 10, it is considered 2 races.
Bottomline is: 5 is a race.
Solution for 7 races:
- Split the 25 men into 5 groups and run them separately and you get top 5.
- Lets call them A1 to A5, B1 to B5 .... E1 to E5.
- Now conduct race between A1,B1, C1, D1, E1. (6th race).
- Assume that the winners are in the same order (A1, B1, C1, D1, E1).
- Now we have the fastest runner who is A1.
- Next conduct the race between A2, A3, B1, B2 and C1 for the second and third position.
- The winner of this race is the second and runner up is the third.
Reason: After 6th race, we can completely eliminate group D and E out of 2nd and 3rd position. Similarly A/B/C-4 and 5. B3 and C3 also cannot contend. C2 is also not eligible for even 3rd position since there are 2 guys faster than him (B1 and C1). So the left over for the 2nd and 3rd position are A2, A3, B1, B2 and C1.
Nice ashok....
Consider your solution when the actual fastest guys are A1,C1,C2
In that case I believe your last race would
be among A2,A3,B1,C1,C2...
Can you rephrase your steps so as to not assume a particular order of wins...
But I guess you get it...
Another solution I had was:
5 races, pick up the best horses, run them all in a 6th race, we know
the topper. Lets say the topper belongs to group A. and the second best
guy in this race belongs to group B and the third best belongs to group
C.
Conduct a 7th race comprising of:
1. From group A take the 2nd and the 3rd fastest horses.
2. From group B take the *second* fastest horse.
3. From group C take the 1st (that is i.e., the one that
participated on the 6th race) and 2nd fastest horse.
There are 2 possibilities:
--------------------------
pick up the 1st and 2nd in this race 7th race.
1. If the 1st horse is the horse that we chose from group B,
then it becomes the 3rd fastest horse among the 25 and
the 2nd fastest is the topper of group B.
2. If the 1st horse isn't the one from group B, then treat the
1st in this 7th race as the 2nd fastest horse among the 25
and consider the 2nd horse in 7th race, if it is the one from
group B, ignore him and the topper of group B becomes the second
best horse. If not, the 2nd horse in the 7th race becomes the
3rd best.
Guess it involves one additional step of reasoning though...
ok that second solution doesn't work...
Manikam,
I think you are wrong with your solution. After the 7th race, in the 2nd case, if the 2nd horse is not from group-B you cannot conclude any thing. Because if A2 comes 1st of 7th race and A3 comes 2nd, then you would not be able to conclude whether A2 and A3 is faster or slower than B1 (since B1 is not in the 7th race).
There is no need to have C2 in the 7th race at all since, from the previous 6 races it is *VERY* clear that ahead C2 there are 3 guys (A1, B1, and C1). So the contest for 2nd and 3rd position is between A2, A3, B1, B2 and C1.
Hope I am not wrong.
Yep, you are right. Thats what I meant when I said "ok that second solution doesn't work..."
Post a Comment
<< Home