A new algorithm for the four counterfeit coins problem


Ivica Bošnjak




We consider the problem of determining the minimum number of weighings which suffice to find the counterfeit (heavier) coins in a set of n coins given a balance scale and the information that there are exactly four heavier coins present. A sequential algorithm is constructed for which the maximum number of steps differs by at most one from the information-theoretical lower bound.