A PREDETERMINED ALGORITHM FOR DETECTING A COUNTERFEIT COIN WITH A MULTI-ARMS BALANCE

We consider the classical problem of searching a light coin in a set o f n coins, n - 1 of which have the same weight. The weighing device is a balance scale with r greater than or equal to 2 pans that, when r e qually sized subset of coins are weighted, indicates the eventual subs et containing the light coin. We give a predetermined algorithm that r equires the minimum possible average number of weighings for almost al l values of n. (C) 1998 Elsevier Science B.V. All rights reserved.