Treffer: Searching for two counterfeit coins with two-arms balance

Title:
Searching for two counterfeit coins with two-arms balance
Authors:
Wen An Liu, Zan Kan Nie, Wei-Guo Zhang
Source:
Discrete Applied Mathematics. 152:187-212
Publisher Information:
Elsevier BV, 2005.
Publication Year:
2005
Subject Terms:
Information-theoretic bounds, Permutations, words, matrices, Worst-case sequential algorithm, Combinatorial search, Applied Mathematics, 0211 other engineering and technologies, Discrete Mathematics and Combinatorics, 0102 computer and information sciences, 02 engineering and technology, Two counterfeit coins problem, counterfeit coins problem, 01 natural sciences, combinatorial search
Document Type:
Fachzeitschrift Article
File Description:
application/xml
Language:
English
ISSN:
0166-218X
DOI:
10.1016/j.dam.2005.03.009
Rights:
Elsevier Non-Commercial
Accession Number:
edsair.doi.dedup.....91d1e40d87d1495ac3d9a1e9a80a2ec8
Database:
OpenAIRE

Weitere Informationen

The paper deals with a variant of the classical problem of locating \(d\) counterfeit coins out of a set of \(n\) coins, \(n-d\) of which are good coins having the same weight. In particular, the model with two counterfeit coins is considered, one of them being heavier and the other one lighter then the good ones, such that the two counterfeit coins together have the same weight as two good coins. It is proven that the information-theoretic lower bound \(U(k)= \max\{ n\mid n(n-1)\leq 3^k\}\) for the number of coins for which the \(k\) weighings suffice is achievable for even integers greater than 2. For odd integers greater than 1, it is shown that the bound \(U(k)\) can be approximated arbitrarily well. Finally, the authors mention how methods used here can be applied on some similar models.