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.
Devise an algorithm to solve the problem of Exercise using three comparisons in the worst case.
Exercise: One of four 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. Prove that no algorithm exists that can meet this lower bound.