
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