Abstract:

The following weighting problem is considered: determine two counterfeit coins which are heavier than good coins in a set of n coins of the same appearance using only an equal arms balance. Let L^{(2)}(n) denote the minimum number of weighings necessary when exactly two of n coins are known to be  defective. For all n\geq 2, it satisfies \lceil \log_3\binom{n}{2}\rceil \leq L^{(2)}(n)\leq\lceil \log_3\binom{n}{2}\rceil+1. It was conjectured that the lower bound is always achieved. In this paper, using an novel algorithm, we improve on the range of n for which the lower bound is reached.

Key words: combinatorial search, group testing, weighting problem, two counterfeit coins