Coins with Arbitrary Weights

Noga Alon, Dmitry N. Kozlov

Research output: Contribution to journalArticle

3 Scopus citations

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 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).

Original languageEnglish (US)
Pages (from-to)162-176
Number of pages15
JournalJournal of Algorithms
Volume25
Issue number1
DOIs
StatePublished - Oct 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Coins with Arbitrary Weights'. Together they form a unique fingerprint.

  • Cite this