Searching for two counterfeit coins with two-arms balance Original Research Article

The following search model of a coin-weighing problem is considered: G has n coins, image of which are good coins of the same weight image, one counterfeit coin of weight image is heavier and another counterfeit coin of weight image is lighter (image). The weighing device is a two-arms balance. Let image be the number of coins for which k weighings suffice to identify the two counterfeit coins by algorithm image and let image be the information-theoretic upper bound of the number of coins; then, image. One is concerned with the question whether there is an algorithm image such that image for all integers k. It is proved that the information-theoretic upper bound image is always achievable for all even integer image. For odd integer image, 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.