Searching for two counterfeit coins with two-arms balance
The following search model of a coin-weighing problem is considered: G has n  coins, n-2 n - 2 of which are good coins of the same weight wg w g , one counterfeit coin of weight wh w h is heavier and another counterfeit coin of weight wl w l is lighter (wh+wl=2wg w h + w l = 2 w g ). The weighing device is a two-arms balance. Let N A ( k ) be the number of coins for which k  weighings suffice to identify the two counterfeit coins by algorithm A A and let U(k)=max{n?n(n-1)?3k} U ( k ) = max { n ? n ( n - 1 ) ? 3 k } be the information-theoretic upper bound  of the number of coins; then, N A ( k ) ? U ( k ) . One is concerned with the question whether there is an algorithm A A such that N A ( k ) = U ( k ) for all integers k . It is proved that the information-theoretic upper bound U(k) U ( k ) is always achievable for all even integer k?4 k ? 4 . For odd integer k?3 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.
combinatorial search two counterfeit coins problem worst-case sequential algorithm information-theoretic bounds