Name
Abstract | ||
|---|---|---|
The following search model of a coin-weighing problem is considered: G has n coins, n - 2 of which are good coins of the same weight wg, one counterfeit coin of weight wh is heavier and another counterfeit coin of weight wl is lighter (wh + wl = 2wg). The weighing device is a two-arms balance. Let NA(k) be the number of coins for which k weighings suffice to identify the two counterfeit coins by algorithm A and let U(k) = max{n | n(n - 1) ≤ 3k} be the information-theoretic upper bound of the number of coins; then, NA(k) ≤ U(k). One is concerned with the question whether there is an algorithm A such that NA(k) = U(k) for all integers k. It is proved that the information-theoretic upper bound U(k) is always achievable for all even integer k ≥ 4. For odd integer k ≥ 3, we establish a general method of approximating the information-theoretic upper bound arbitrarily. The ideas and techniques of this paper can be employed easily to settle other models of two counterfeit coins. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1016/j.dam.2005.03.009 | Discrete Applied Mathematics |
Keywords | Field | DocType |
weight wg,two-arms balance,weight wh,weight w,weight wl,following search model,counterfeit coin,integer k,good coin,algorithm a,coin-weighing problem,k weighings,integers k,n coin,general method,odd integer k,information-theoretic upper bound u,combinatorial search,upper bound | Information theory,Integer,Discrete mathematics,Combinatorics,Upper and lower bounds,Counterfeit,Combinatorial search,Mathematics | Journal |
Volume | Issue | ISSN |
152 | 1-3 | Discrete Applied Mathematics |
Citations | PageRank | References |
3 | 0.41 | 17 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wen An Liu | 1 | 65 | 12.61 |
| Wei-Guo Zhang | 2 | 557 | 39.22 |
| Zan-Kan Nie | 3 | 139 | 9.59 |