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.