BALANCE SCALE SORTING,
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 07, 1955
- Accession Number
- AD0604945
Entities
People
- S. S. Cairns
Organizations
- RAND Corporation