Question

2. (10%) Suppose that among n identical-looking coins, one is fake. With a balance scale, we can compare any two sets of coins. That is, by tipping to the left, to the right, or staying even, the balance scale will tell whether the two sets weight the same, or which of the two sets is heavier than the other but not by how much. Please use the prune and search strategy to design an efficient algorithm for detecting the fake coin (6%). For simplicity, we assume that the fake coin is lighter than the genuine one. Please also analyze the number of weighting needed by your algorithm in worst case (4%).

Answer 1

Answer:
As stated in the question the counterfeit coin is lighter than the original coin. Desired algorithm to find counterfeit coin is given below:-

STEP 1: if n== even, divide the coins into 2 equal groups of n/2 and n/2.
STEP 2: check which group is lighter, lighter group would be the one which contains the counterfeit coin.
We will have to repeat all the steps mentioned here for the subgroup as well.
STEP 3: if n==odd, randomly remove one coin from the group and then divide remaining (n-1) into 2 groups of
(n-1)/2 each, there could be two possibility both group are equal in this case one coin which was removed
is counterfeit coin. else follow same step as above for lighter weigh group of (n-1)/2
STEP 4: one number of element ==2 check and find the lighter coin among the two as the counterfeit coin.

From the above algorithm its clear that on every weighing steps we are able to decrease the number of elements to half, so on worst case scenario it can become
< k/2+k/4+k/6..... 2 (number of terms in above algorithm, let it be m)
2n+1 < 3^m
n < (3^m-1)/2
log(2n+1) < m*log(3) //taking log both sides
log(2n+1)/log(3) < m

So worst case number weighing for n coins would be m = log(2n+1)/log(3)


(plz give me a thums up...if my answer helped you and if any suggestion plz comment, Yr thums up boost me)