The following question is on races, similar to the previous post…
The tricky question, given 25 horses of different caliber, intent is to find best 3 horses in minimum possible number of races under the constraint that only 5 horses are allowed per race.
We can generalize the question as, set of N2 horses and allowed N horses per race. How many minimum races are required to find best 3 horses?
Hint: Generalisation has the clue. You need to be aware of matrix optimization techniques. Also try, how to find 4th best horse?
3 comments:
7 races should do the job. Lets assume a1, a2, a3, a4, a5, b1, b2, b3, b4, b5, c1, c2, c3, c4, c5, d1, d2, d3, d4, d5, e1, e2, e3, e4, e5 are the horses belonging to five groups a, b, c, d, e.
First race all 5 individual groups: 5 races
Now assume a1, a2, a3, b1-b3, c1-c3, d1-d3, e1-e3 are the top 3 in each group in the same order(a1 - fastest).
Now race a1, b1, c1, d1 and e1 - 1 race -> this should give us the fastest horse in all. Assume a1 - is fastest. Eliminate a1 from the group. Next assume b1 - 2nd, c1- 3rd, d1- 4th, e1- 5th in this race. So this eliminates d1, e1 and d2,d3,e2,e3 from the race.
Now we need to race a2,a3,b1,b2,c1 - last race. Here the top two horses would be second and third respectively.
So 7 races will do.
For N2 horces answer will be N + 2
see the logic above.
What a shame, no response from the "author"...
Post a Comment