Searching for two counterfeit coins with two-arms balance (Q2576348)

The paper deals with a variant of the classical problem of locating \(d\) counterfeit coins out of a set of \(n\) coins, \(n-d\) of which are good coins having the same weight. In particular, the model with two counterfeit coins is considered, one of them being heavier and the other one lighter then the good ones, such that the two counterfeit coins together have the same weight as two good coins. It is proven that the information-theoretic lower bound \(U(k)= \max\{ n\mid n(n-1)\leq 3^k\}\) for the number of coins for which the \(k\) weighings suffice is achievable for even integers greater than 2. For odd integers greater than 1, it is shown that the bound \(U(k)\) can be approximated arbitrarily well. Finally, the authors mention how methods used here can be applied on some similar models.