Advanced fake-coin problem There are n ≥ 3 coins identical in appearance; either all are genuine or exactly one of them is fake. It is unknown whether the fake coin is lighter or heavier than the genuine one. You have a balance scale with which you can compare any two sets of coins. That is, by tipping to the left, to the right, or staying even, the balance scale will tell whether the sets weigh the same or which of the sets is heavier than the other, but not by how much. The problem is to find whether all the coins are genuine and, if not, to find the fake coin and establish whether it is lighter or heavier than the genuine ones.
(a) Prove that any algorithm for this problem must make at least ceil(log base 3 (2n + 1)) weighings in the worst case.(b) Draw a decision tree for an algorithm that solves this problem for n = 3 coins in two weighings.