Given a set of m coins out of a collection of coins of k unknown distinct 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 regular balance beam. Let m(n, k) denote the maximum possible number of coins for which the problem can be solved in n weighings. It is known that m(n, 2) = n(1/2+o(1))n. Here we determine the asymptotic behavior of m(n, k) for larger values of k. Surprisingly it turns out that for all 3 ≤ k ≤ n + 1, m(n, k) is much smaller than m(n, 2) and satisfies m(n, k) = Θ(n log n/log k).
All Science Journal Classification (ASJC) codes
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics