In: Computer Science
Suppose there are n (>=3) gold bullions, where one of them is fake. However, we do not know whether the fake one is heavier or lighter than the genuine ones. All the genuine ones weigh the same. In this problem, you are asked to use a balance scale to find the fake one in o(n) steps (little-o). NO pseudo-code is needed, only describe your answers to the following questions: (25pts)(1) What are your bases cases? How do you solve your base case(s)?(2) For non-base cases, how do you divide and weigh to reduce the given problem into subproblem(s)?(3) Derive your recurrence relation and justify that the number of steps of using the scale is o(n).
Base Case :
If n = 3 , We have 3 gold bullions and we need to check the weight of any 2 bullions.
Suppose Bullions are A,B,C , If A is equal to B , fake bullion is C otherwise genuine bullion is C and we have to make another comparison.
Non Base Case :
The first part is to solve the puzzle in k weighings given 3^k , (3^k+1)/2 of which could only contain a heavier gold bullions and (3^k-1)/2 of which could only contain a lighter gold bullions (or vice versa):
Second Part