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
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)
4 comments:
there are 81 horses. you need to select the first best 6 horses. Each time only 9 horses can participate. how many minimum no. of races you require
There is a problem with this. As you only need the three fastest horses, you can discard the slower ones earlier in the algorithm, which makes that you need only 7 instead of 8 races.
First 5 races: get 5x3fastest, plus order of arrival; discard 2 slowest of each group:
1: 1.1 1.2 1.3
2: 2.1 2.2 2.3
3: 3.1 3.2 3.3
4: 4.1 4.2 4.3
5: 5.1 5.2 5.3
6th race among fastest of each group: keep only 3 groups that win this, say w.l.g.:
1: 1.1 1.2 1.3
2: 2.1 2.2 2.3
3: 3.1 3.2 3.3
-> Will know the fastest, say 1.1, leave him out of next races, will be left:
1.2 1.3 2.1 2.2 2.3 3.1 3.2 3.3
Say that 3.1 was slower than 2.1, then it will certainly not be second, max third. 3.2 and 3.3 therefore cannot be among the fastest three, discard them. Will be left:
1.2 1.3 2.1 2.2 2.3 3.1
Same for 2.3: cannot be among the fastest three, discard, only five will be left:
1.2 1.3 2.1 2.2 3.1
Set up a 7th race among these, fastest 2 are second and third of the 25.
@Kevin Yes You Right , I was Also Aware of Such Optimize Solution but forgot to update the same , so thanks fro providing nice solution Keep it Up :)
Cheers!!!
Shashank
Great post!
Also found a good explanation here for the same puzzle:
25 horses 5 tracks puzzle
Post a Comment