The geometry of coin-weighing problems

Noga Alon, Dmitry N. Kozlov, Van H. Vu

Abstract

Given a set of m coins out of a collection of coins of k unknown distinct weights, the authors 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. They show that m(n,2)=n/sup ( 1/2 +o(1))n/, whereas for all 3/spl les/k/spl les/n+1, m(n,k) is much smaller than m(n,2) and satisfies m(n,k)=/spl Theta/(n log n/log k). The proofs have an interesting geometric flavour; and combine linear algebra techniques with geometric probabilistic and combinatorial arguments.
BibTeX
@inproceedings{alon1996geometry,
  author = {Noga Alon and Dmitry N. Kozlov and Van H. Vu},
  title = {{The geometry of coin-weighing problems}},
  booktitle = {FOCS},
  year = {1996},
  doi = {10.1109/sfcs.1996.548511},
}

Loading related content...

Figure