TY - JOUR
T1 - Coins with Arbitrary Weights
AU - Alon, Noga
AU - Kozlov, Dmitry N.
N1 - Funding Information:
* A preliminary version of part of this paper appears in the Proceedings of the 37th FOCS, IEEE 1996). ²Research supported in part by a USA—Israeli BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences. E-mail: [email protected]. ³E-mail: [email protected].
PY - 1997/10
Y1 - 1997/10
N2 - 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).
AB - 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).
UR - http://www.scopus.com/inward/record.url?scp=0346441509&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0346441509&partnerID=8YFLogxK
U2 - 10.1006/jagm.1997.0871
DO - 10.1006/jagm.1997.0871
M3 - Article
AN - SCOPUS:0346441509
SN - 0196-6774
VL - 25
SP - 162
EP - 176
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 1
ER -