Three counterfeit coins


Ratko Tošić




We consider the problem of ascertaining the minimum number of weighings which suffice to determine all counterfeit (heavier) coins in a set of $n$ coins of the same appearance, given a balance scale and the information that there are exactly three heavier coins present. An optimal procedure is constructed for an infinite set of $n$'s and a suboptimal procedure for another infinite set of $n$'s. We also consider a slightly modified problem, i.e., the case when we are given a certain number (not greater than $n$) of additional coins for which we know that they are all good (not counterfeit). For that case, and arbitrary $n$, we determine an upper bound for the maximum number of steps (weighings) of an optimal procedure which differs by just two from the information-theoretical lower bound. The proof is given by an effective construction of a procedure.