Accession Number : AD0604945

Title :   BALANCE SCALE SORTING,

Corporate Author : RAND CORP SANTA MONICA CALIF

Personal Author(s) : Cairns,S. S.

Report Date : 07 SEP 1955

Pagination or Media Count : 40

Abstract : Given (1) a set W of n objects, indistinguishable save that the members of a subset H of h objects are slightly heavier than the rest (2) a balance scale, one seeks weighing programs minimizing either (Problem M(n,h)) the maximum number of weighings which may be required to cull out H or (Problem E(n,h)) the expected number of such weighings. Problem M(n,1) is a familiar puzzle. Problem E(n,1) was solved under various hypotheses. Problem M(n,2) was partially solved. Some aspects of it require further investigation. The paper could be used as a basis for more research on M(n,h) and E(n,h) in general. Some of the techniques involve manipulations of series which may be applicable to other combinatorial problems. (Author)

Descriptors :   (*LINEAR PROGRAMMING, OPTIMIZATION), SET THEORY, PROBABILITY, SERIES(MATHEMATICS), COMBINATORIAL ANALYSIS, INEQUALITIES, MATHEMATICAL PROGRAMMING

Distribution Statement : APPROVED FOR PUBLIC RELEASE