There are 25 horses and only five tracks in a race (i.e., you can race 5 horses at a time). There is no stop clock !! Assume that there are no ties.
1: What is the minimum number of races needed to determine the 3 fastest horses in order from fastest to slowest ?
2: ..... to find out the fastest one ?
3: ..... to rank all of them from fastest to slowest ?
4: ..... to find the top k fastest horses ?
Subscribe to:
Post Comments (Atom)
1 comment:
This is what I have worked upon...
Assuming that all the horses run all their races at identical speeds.
* min number of races needed to determine the 3 fastest from fastest to slowest in that order
sol:-
1. Group the 25 horses into 5 equal groups (so each group has 5 horses).
2. Race each of the groups to get 5 toppers in each of those groups.
3. Race the toppers once more and you get the fastest out of 25. I will call him I and the second fastest as II and third fastest as III (II & III are not the second and third fastest out of 25).
4. From the group that had I we have 4 remaining horses that need to be tested with the II and III.
5. Race between the 4 remaining horses and horse II.
6. If horse II comes top in this race (this horse would be the second fastest out of 25)then we need one more race between the 4 remaining and horse II to determine the third fastest out of 25. Else we have our 3 fastest.
7. We can surely determine the 3 top ranked horses in 8 races.
* min number of races to determine the fastest one
sol:-
6 races (steps 1 thru 3 described above)
* min number of races to rank all of them
sol:-
1. I can re-phrase this question to ask the min number of races to get 25 fastest horses.
2. You need 6 races to get the fastest ranked (steps 1 thru 3).
3. After that every race will give you the next fastest.
4. We can continue this till we have got the 20 fastest horses. After that we just need 1 race to rank the remaining 5.
total = 6 (to get rank 1) + 19 (to get rank 2-20) + 1 (to get rank 21-25) = 26
* min number of races to get k fastest horse
sol:-
5 + k (for k <= 20 )
26 (otherwise)
Please let me know what you think of these.
Thanks,
Post a Comment