OPTIMAL DETECTION OF A COUNTERFEIT COIN WITH MULTI-ARMS BALANCES

We consider the problem of locating a light coin out of a set containi ng n coins, n - 1 of which have the same weight. The weighing device i s a balance with r greater than or equal to 2 pans that, when r equall y sized subset of coins are weighted, indicates the subset eventually containing the light coin. We give an algorithm to find the counterfei t coin that requires the minimum possible average number of weighings. All previous results on this problem considered two-arms balances onl y.