Let us say you have
n objects of which you want to chose the
p most valuable objects. Now the problem is, there is no quantitative way of defining value, and you are not really an expert on qualitatively ranking all these objects. However, there is a ranking program available to rescue you. The ranking program takes a set of objects and ranks them as 1st, 2nd etc.. The only caveat is that the ranking program takes in at most
k (k >= 2) objects at one time. What is the minimum number of times you have to use the ranking program to chose the best
p objects? Explain how you'll go about achieving this. For convenience, assume that
k divides
n exactly
(n mod k = 0), p < k.
To give a concrete example, assume that you are an editor that needs to chose the 3 best articles among a 100 that are submitted. You can send them to reviewers each of who will rank at most 5 articles. What is the minimum number of reviewers that you need? (If you contact the same reviewer multiple times, each contact need to be accounted for, of course.
)
Print