E. Suppose that you have a two pan balance scale which you use by putting things
ID: 3730257 • Letter: E
Question
E. Suppose that you have a two pan balance scale which you use by putting things into both pans, and then seeing which way the balance tips to see which pan is heavier (or if they are equal if the balance does not tip). You are given a set of n coins and told that exactly one of them is counterfeit. You are also told that the counterfeit coin will be the one of them which is heavier than the others. Examine the algorithm FindCounterfeit, presented on the next page. Explain why this algorithm will determine where the counterfeit coin is. (It may help to try it out on an example problem with three or four coins, and where the counterfeit coin is in various spots.)Explanation / Answer
As given N is the number of coins and we are dividing it into 3 groups containing floor(N/3) coins. There are three groups containing the equal number of coins. Firstly we compare two group and check whether these two groups are of equal weight or not. If they not equal and the first group is containing more weight then we will start recursively searching it in the left group else if the right group contains more weight than we will search in the right group. The condition may come that the weight of the first and second is same then the possibility of having counterfeit coin will be in the third group.
1. The best case to find a counterfeit coin is to be Ceil(log3N)
2. For the Worst case, we need to design a decision tree with at least (2N+1) leaves for the output and have utmost 3k . Therefore we need k>log3(2N+1) weighing to find the counterfeit coin.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.