Suppose you work at Gringotts bank and are given a pile of N gold coins, any number of which may be lighter than they should be, this indicating that they are fakes. Your job is to determine which of the N coins are fake, and which are genuine. You have available a balance scale that can compare the weight the weight of piles of coins. This balance scale give three possible answers: the two piles weight the same, the left pile is heavier, or the right pile is heavier. You also have available a pile of good coins. You would eventually like to develop an algorithm to allow you to find all of the fake coins in as few weights as possible.

For this problem I do not want you to find an algorithm. Instead I want you to think about how fast an algorithm it might be possible to make. The speed of an algorithm will be measured by the number of weights in the worst case.

The 3 questions below guide through a decision tree argument to prove a lower bound on the worst case running for this problem.

a) How many possible answers are there for an input size of N coins?

b) What is the maximum number of leaves in a decision tree of height H for this problem?

c) Using these two equations explain and solve for a lower bound on any possible algorithm (please simplify your bound).