Five counterfeit coins

Abstract

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 five heavier coins present. For an infinite set of n's we determine an upper bound for the maximum number of steps of an optimal procedure which differs by just two from the information-theoretical lower bound. We also consider a slightly modified problem, i.e. the case when we are given a certain number (not greater than 2n-3) 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 of an optimal procedure which differs by just seven from the information-theoretical lower bound. © 1989.