COINS WITH ARBITRARY WEIGHTS

Given a set of m coins out of a collection of coins of k unknown disti nct weights, we wish to decide if all the m given coins have the same weight or not using the minimum possible number of weighings in a regu lar balance beam. Let m(n, k) denote the maximum possible number of co ins for which the problem can be solved in n weighings. It is known th at m(n,2) = n((1/2+o(1))n). Here we determine the asymptotic behavior of,rr(n, k) for larger values of k. Surprisingly it turns out that for all 3 less than or equal to k less than or equal to n + 1, m(n, k) is much smaller than m(n,2) and satisfies m(n, k) = Theta(n log n/log k) . (C) 1997 Academic Press.