Data Structures, Algorithms, & Applications in C++
Chapter 18, Exercise 1
First consider the case when we simply want to detect the presence
of a light counterfeit.
If m is even, divide the coins into two sets, each set having
n/2 coins. Compare the weight of the two sets.
If the two sets have the same weight, there is no counterfeit coin;
and if one set is lighter, there is a counterfeit coin. The number
of weight comparisons is one. If n is odd, remove one coin and apply the test
for an even number of coins to the remaining n-1 coins. If this test
detects the presence of a counterfeit coin, we are done.
If no counterfeit coin is detected in the set of n-1 coins,
there is still the possibility that the coin we removed is counterfeit.
Compare the weight of this coin with that of any of the remaining
n-1 coins. If both weigh the same, no coin is counterfeit. Otherwise,
the lighter coin is counterfeit. So when n is odd, we need to
make either one or two weight comparisons.
Next consider the case when we want to identify the counterfeit coin.
If n is <= 3, we can identify the counterfeit with at most
two weight comparisons as described in Example 19.1. If n > 3,
we proceed as above. With one weight comparison, the problem is either
solved (there is no counterfeit) or reduced to one of size
floor(n/2). If two weight comparisons are done (possible only when
n is odd, the problem is solved).
The maximum number of weight comparisons is
ceil(log2n).