Searching for two counterfeit coins with two-arms balance (Q2576348)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Searching for two counterfeit coins with two-arms balance |
scientific article |
Statements
Searching for two counterfeit coins with two-arms balance (English)
0 references
27 December 2005
0 references
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.
0 references
combinatorial search
0 references
counterfeit coins problem
0 references
0 references