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 -