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 ?
We group the 25 horses in 5 groups each containing 5 horses.In each of first five races we will rank each five horsesA, B,C,D and E ( A : fastest and E: slowest) in the group.
1A 1B 1C 1D 1E
2A 2B 2C 2D 2E
3A 3B 3C 3D 3E
4A 4B 4C 4D 4E
5A 5B 5C 5D 5E
In the sixth race ( among the first of each group) we will get the fastest horse and rank these five horses 1A,2A,3A,4A & 5A (1A : fastest and 5A slowest)
Similarly .just select the fastest of the remaining horses from each row for the race.
Now we have got the fastest horse 1A and will also set nomenclature for each horses.
The fastest of the remaining horses in the row will take part.For e.g. the seventh race will be between 1B & 2A (no need to run 3A,4A & 5A)for determining
2nd fastest horse.
The 8th race will determine the third place and it will be between 1C and 2B ( in case 1B wins 7th race) or among 1B,2B & 3A ( in case 2A wins 7th race).
The 9th race will determine the 4th place and the 10th race will determine 5th place.
And moving on 25 th race will determine 20th place.The 26th race will tel the remaining 5 ranks.
Follow Up minimum number of races needed to find
1:....... to rank all of them from fastest to slowest ?
2:....... to find the top k fastest horses ?
* min number of races to rank all of them
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
5 + k (for k <= 20 )