Establishing a Pecking Order

Extract

This study was suggested by C. S. Ogilvy’s “Tomorrow’s Math”, which poses: “A weighing problem which has been going the rounds of some mathematical communities is the problem of the balls. Given n distinguishable balls, of which it is known that no two have the same weight, it is required that they be arranged in order of magnitude by weighings of one against another in a pan balance scale (no weights). What is the smallest number of weighings, as a function of n, which will always suffice? What strategy (procedure) does one adopt to achieve this minimum? Some assortments (depending on luck) will be more quickly ordered than others. Will the best strategy automatically minimize the expected number of weighings if the original ordering is random?”