Optimal detection of two counterfeit coins with two-arms balance

✍ Scribed by Liu Wen-An; Nie Zan-Kan

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 430 KB
• Volume: 137
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00343-3

✦ Synopsis

We consider the following coin-weighing problem: suppose among the given n coins there are two counterfeit coins, which are either heavier or lighter than other n -2 good coins, this is not known beforehand. The weighing device is a two-arms balance. Let N A (k) be the number of coins from which k weighings su ce to identify the two counterfeit coins by algorithm A and U (k) = max{n | n(n -1) 6 3 k } be the information-theoretic upper bound of the number of coins then N A (k) 6 U (k). We establish a new method of reducing the above original problem to another identity problem of more simple conÿgurations. It is proved that the information-theoretic upper bound U (k) are always achievable for all even integer k ¿ 1. For odd integer k ¿ 1, our general results can be used to approximate arbitrarily the information-theoretic upper bound. The ideas and techniques of this paper can be easily employed to settle other models of two counterfeit coins.