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.