Abstract
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 above problem can be solved in n weighings. We show that m(n, 2) = n( 1/2 +o(l))n, whereas 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). The proofs have an interesting geometric flavour, and combine Linear Algebra techniques with geometric, probabilistic and combinatorial arguments.
Original language | English (US) |
---|---|
Pages (from-to) | 524-532 |
Number of pages | 9 |
Journal | Annual Symposium on Foundations of Computer Science - Proceedings |
State | Published - 1996 |
Externally published | Yes |
Event | Proceedings of the 1996 37th Annual Symposium on Foundations of Computer Science - Burlington, VT, USA Duration: Oct 14 1996 → Oct 16 1996 |
All Science Journal Classification (ASJC) codes
- Hardware and Architecture