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

You are given n = 2^k 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

There are n=2^k coins.
a) We divide the coins in to 4 sets, n1,n2,n3 and n4. We compare n1 and n2, then we compare n1 and n3.

There are 4 cases:

1) n1=n2, n1=n3, the defective coin is in n4.
2) n1=n2, n1!=n3, the defective coin is in n3.
3) n1!=n2, n1=n3, the defective coin is in n2.
4) n1!=n2, n1!=n3, the defective coin is in n1.

So we reduced the size from 2^k to 2^(k-2) with two comparisions.

b) We reduced the size by 4 with 2 comparisions. Finally we should reduce the size to 1, so this takes k comparisions. As n should be reduced by 2^k times.

c) If k is a multiple of 2, then we are finally left with defective coin after k comparisions. But if k is odd number, then finally we will be left with two coins(p1 and p2). Here we should compare p1 with one of the fair coin we kept aside, if they are same then p2 is defective, otherwise p1 is defective. Even here it takes k comparisions.

This algorithm does not work for n=2. It is not possible to find the defective coin in this case.