Question

In: Computer Science

Suppose there are n (>=3) gold bullions, where one of them is fake. However, we do...

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).

Solutions

Expert Solution

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):

  • For 3^0=1 gold bullions (split 0 and 1), we require no weighings.
  • For 3^(k+1) (split 3^(k+1)+1/2 and 3^(k+1)-1/2), we weigh (3^k+1)/2 from group A and (3^k-1)/2 from group B against another (3^k+1)/2 from group A and (3^k-1)/2 from group B (leaving unweighed (3^k-1)/2 from group A and (3^k+1)/2 from group B). If the weighed are equal, we recursively solve the problem for the unweighed group. Otherwise, we've whittled down the suspects to the group A on one side and the group B on the other, so we instead recursively solve the puzzle for those.

Second Part

  • For (3^(k+1)+1)/2 and an additional 'normal' gold bullions, we weigh (3^k+1)/2 against (3^k-1)/2 plus the 'normal' one, leaving (3^k+1)/2 unweighed. If the weighed are equal, we recursively solve the problem for the unweighed group. Otherwise, we use the solution from the first part for the (3^k) weighed .
  • For (3^(k+1)-1)/2 with no additional 'normal' gold bullions, we weigh (3^k-1)/2 against another (3^k-1)/2 . If the weighed are equal we use the solution above on the remaining (3^k+1)/2 ; otherwise we add an unweighed gold bullions (now known to be 'normal') to the 3^k-1 weighed and again use the solution from the first part .

Related Solutions

What is wheezing where do we hear them?
What is wheezing where do we hear them?
Suppose we live in a monocentric city where streetcars have replaced horse carts. However, the streetcars...
Suppose we live in a monocentric city where streetcars have replaced horse carts. However, the streetcars have begun to break down and slowed in their reliability and speed. Compared to fully functioning streetcars, we expect that Select one: a. residents will outbid agricultural users further from the city center b. residential areas will grow c. city wages will increase d. land rent at the city center will increase
What are the ledgers, why do we use them? And then HOW do we use them,...
What are the ledgers, why do we use them? And then HOW do we use them, how does information get into them how do balances get extracted. And then what should the balances for various accounts be, i.e. assets, liabilities, expenses, revenues, equity, dividends. Why SHOULD they have a particular balance as either debit or credit.
Suppose we have an economy where the population is the same every period, Nt = N...
Suppose we have an economy where the population is the same every period, Nt = N and the money supply is increasing by z each period, i.e., Mt = zMt−1. The government uses the money it creates each period to finance a lump-sum subsidy of a ∗ goods to each old person. (a) (10 points) Find the equation for the budget set of an individual in the monetary equilibrium. Graph it. Show an arbitrary indifference curve tangent to the set...
Suppose we have the following vectorial equation c = na x b where n is a...
Suppose we have the following vectorial equation c = na x b where n is a constant, and c, a, b are vectors Givens n = -1 a = 2i – j a) Determine the direction and size of the vector c if b = 2i b) Determine the direction and size of the vector c if b = 2k c) Determine the direction and size of the vector c if b = 2i – k I really need the...
What are chi distributions, how do we use them, when do we use them, and why...
What are chi distributions, how do we use them, when do we use them, and why are they important?
Where in the Universe do we observe the ordinary matter? Select one: a. as galaxies and...
Where in the Universe do we observe the ordinary matter? Select one: a. as galaxies and intergalactic gas b. throughout the galaxies and in the extended halos around them c. throughout the observable universe
suppose we have string like jason-458164888 how do we check if the numbers are vaild where...
suppose we have string like jason-458164888 how do we check if the numbers are vaild where the first number should be 4 and length of 9. use simple program.
For Karl Marx, what we do is who we are. However, under advanced capitalism that is...
For Karl Marx, what we do is who we are. However, under advanced capitalism that is only true of a very few of us. According to Marx, under capitalism, work has become something that you do, not who you are. Capitalism has thus robbed us of ourselves. How does the film Happiness by Steven Cutts reflects Karl Marx's discussion of alienation and how does it relate to you own life? How can we use Karl Marx's ideas about alienation and...
2. Consider an n-cube, where n = 3. Is it possible to draw this on a...
2. Consider an n-cube, where n = 3. Is it possible to draw this on a two dimensional plane where the lines do not cross? If it is possible, draw it. If not, prove that it isn't possible.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT