Searching for a subset of counterfeit coins: Randomization vs determinism and adaptiveness vs non-adaptiveness

Gianluca De Marco, Dariusz R. Kowalski

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


We are given n coins of which k are heavy (defective), while the remaining n - k are light (good). We know both the weight of the good coins and the weight of the defective ones. Therefore, if we weigh a subset Q ⊆ S with a spring scale, then the outcome will tell us exactly the number of defectives contained in Q. The problem, known as Counterfeit Coins problem, is to identify the set of defective coins by minimizing the number of weighings, also called queries. It is well known that Θ(klog k +1(n/k)) queries are enough, even for non-adaptive algorithms, in case k ≤ cn for some constant 0 < c < 1. A natural interesting generalization arises when we are required to identify any subset of m ≤ k defectives. We show that while for randomized algorithms Θ̃(m) queries are sufficient, the deterministic non-adaptive counterpart still requires Θ(klog k +1(n/k)) queries, in case k ≤ n/2 8; therefore, finding any subset of defectives is not easier than finding all of them by a non-adaptive deterministic algorithm.

Original languageEnglish (US)
Pages (from-to)97-109
Number of pages13
JournalRandom Structures and Algorithms
Issue number1
StatePublished - Jan 2013
Externally publishedYes


  • Adaptive algorithms
  • Algorithms
  • Combinatorial search
  • Counterfeit coins
  • Randomized algorithms

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'Searching for a subset of counterfeit coins: Randomization vs determinism and adaptiveness vs non-adaptiveness'. Together they form a unique fingerprint.

Cite this