You are given n 2k coins all of which look identical Howeve

You are given n = 2k
coins, all of which look identical. However, one of the
coins is defective – it weighs either slightly more or slightly less than the rest (you don’t know which). You also
have at your disposal an electronic equivalence tester, which has two compartments. You may place any set of
objects in each compartment; the tester tells you whether or not the two sets weigh the same. Note that the tester
does not tell you which side is heavier and which one lighter – only whether they weigh the same or not. Your
goal is to determine which of the coins is defective using the tester at most k times. You may assume that k > 1,
that is, n > 2. (Is it possible to find the defective coin when n = 2?) Note that you are allowed to use the tester
only k times, not O(k) or k plus a few more times. You will receive partial credit for slightly worse solutions.
(a) Describe a divide and conquer algorithm for this problem.
(b) Argue that your algorithm uses the tester at most k times.
(c) Prove the correctness of your algorithm, in other words that it always correctly identifies the defective
coin.

Solution

The number of coins are given as n = 2^k. All the coins are identical except one which is defective coin. The algorithm to get the defective coin in 2 turns of a equivalence tester is given as follows:

(a)

The given problem can be solved using a divide and conquer approach. The divide and conquer algorithm works as follows:

The required algorithm is given as follows:

The size of the set of the coins is reduced to 2^(k-2) using two comparisons.

(b)

The size is first reduced by 4 using 2 comparisons of n1, n2, n3, and n4, then the size will be reduced to 1 and in this way the algorithm uses tester k times because number of coins(n) will be reduced by 2^k times.

(c)

The algorithm will find the defective coin after using tester k times if k is a multiple of 2 or even. There will be 2 coins (c1, c2) left for the choice of defective coin in case if k is an odd number.

Compare the coin c1 with the set of fair coins and if both are same, then the coin c2 is defective, otherwise coin c1 will be defective. Here also the algorithm will use the tester k times.

The algorithm cannot determine the defective coin if there are only 2 coins.