On the solution of the general counterfeit coin problem

I read about the counterfeit coin problem with 12 coins and no pre-knowledge about the weight of the odd coin long time ago, but never thought about generalizing it to more coins until recently. The general problem is the following (one can certainly generalize further in other directions): Suppose we have n coins, and that we know there is exactly one counterfeit coin whose weight differs from the rest. Further suppose we have a two-sided balance that detects unequal weight between two sets of coins of equal cardinality. What’s the minimum number of weighing necessary to detect the counterfeit coin?

The solution came from a paper by Bennet Manvel from the 70s. I figured it out myself mostly based on the statements of the lemma in the paper. The answer is that the number of weighings m satisfies
(3^m-3)/2 < n \le (3^m-1)/2. Without going into the technical details of the proof, which involves the subtle difference between having an extra standard coin for comparison or not having it, let me outline the ideas of the proof, from which a weighing strategy can also be established. Note that this does not guarantee yet minimum expected number of weighings with uniformly distributed counterfeit coin position.

First, one can easily show that the number of weighings needed to detect a lighter coin knowing that there is only one lighter than the rest (i.e., we not only know the number of fake coins, but also whether its heavier or lighter) satisfies 3^{m-1} < n \le 3^m. This follows easily from induction and the fact that each weighing can reduce the number of uncertain coins by at most 1/3 factor.

The second step is the most crucial of all: one needs to establish that if each coin is labeled either possible lighter, or possible heavier initially, and we know there is one fake coin, then the minimum number of weighings m satisfies the same bound as above. This requires the following strategy, suppose without loss of generality there are more possibly lighter coins than possibly heavier ones, and for simplicity assuming the total number of coins is a multiple of 3, i.e., n = 3k, then we choose 2a possibly lighter coins and 2b possible heavier coins, such that a+ b =k. Then weigh a p.l. + b p.h. against the other set of a p.l. + b p.h.. The result is divided into three cases, either lhs < rhs, in which case the we know that the bad coin is among the first a p.l. or the last b p.h; the opposite case of rhs < lhs is treated similarly. Finally lhs = rhs implies the the fake one is among the remaining k coins that haven't been weighted. Induction gives the result.

For the third step, assume without loss again that the initial number of coins is a multiple of 3, say 3k. Then we weigh two groups of k coins. Then either we reduce the problem to 2k coins with possibly lighter or heavier label on each, or a problem of k coins of the original kind, i.e., no labeling. An induction finishes it.


About aquazorcarson

math PhD at Stanford, studying probability
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s