You are given

*n* gold coins, and one of them is

fake. Assume that all the coins are

identical, except that the fake coin is

lighter. Given a

balance scale, where you can put a bunch of coins on the left and the right and determine which is heavier, design the

fastest algorithm for determining the fake coin.

Prove that no algorithm can be faster that yours.