Question: Concern the problem of identifying a counterfeit coin (one that is two heavy or too light) from a set of n coins. A balance scale is used to weigh a group of any number of coins from the set against a like number of coins from the set. The outcome of such a comparison is that group A weighs less than, the same as, or more than group B. A decision tree representing the sequence of comparisons done will thus be a ternary tree, where an internal node can have three children.

One of eight coins is counterfeit and is either too heavy or too light. The problem is to identify the counterfeit coin and determine whether it is heavy or light.

a. What is the number of final outcomes (the number of leaves in the decision tree)?

b. Find a lower bound on the number of comparisons required to solve this problem in the worst case.

c. Devise an algorithm that meets this lower bound (draw its decision tree).