A tale of two coins.
01 January 1987
A common phenomenon in combinatorial search theory is that while it is often straightforward to find an optimal procedure to search for one object, it is immensely more difficult to search optimally for two objects. Two examples are the open problems of identifying two counterfeit coins using a balance scale and of identifying two defectives using group testing. In this paper we give a systematic study of identifying two irregulars under various models of a group-testing type device (as opposed to the balance-scale type device which compares two sets instead of testing a set.) We find a gamut of problems with varying degrees of difficulty. We believe that these problems provide a good forum for exploring the boundaries between easy problems and hard problems in combinatorial search theory.