Problem
Consider the following problem:
(a) Suppose we have nine identical-looking coins numbered 1 through 9 and only one of the coins is heavier than the others. Suppose further that you have one balance scale and are allowed only two weighing. Develop a method for finding the heavier counterfeit coin given these constraints.
(b) Suppose we now have an integer n (that represents n coins) and only one of the coins is heavier than the others. Suppose further that n is a power of 3 and you are allowed log3 n weighing to determine the heavier coin. Write an algorithm that solves this problem. Determine the time complexity of your algorithm.