Question

You have n coins that are all supposed to be gold coins of the same weight, but you know that one coin is fake and weighs less than the others. You have a balance scale: you can put any number of coins on each side of the scale, and it will tell you if the two sides weigh the same or which side is lighter if they do not weigh the same.

Can you give a lower bound on the number of weighings needed to discover the fake coin? Draw a decision tree that helps support your answer.

Note: as usual, we are interested in an asymptotic lower bound (something of the form Ω(n^34)). For an extra challenge, we encourage you to find an exact lower bound (say, we need to do at least 36n^34 − 11n^12 weighings). Don’t worry. The real answer will not be as ugly as this example.

Answer 1

Solution for the problem is provided below, please comment if you have any doubts:

Here the problem is there are “n” coins in which one is fake one and remaining have the same weight. We are provided with a balance and it will tell whether the both sides are same or which side is heavier/lighter.

The solution for the problem can be found by dividing the coins into equal half, if it is even and into equal half after removing one from the coins if “n” is odd, in case of even “n”, there should be one hand has less weight since it contain a lighter fake coin. Now process the same procedure on the lighter set of coin. In case of odd “n”, there are two chances are there, it can be happened as that of even “n”, and it can show same weight on both hands, in that case the removed coin should be the fake coin.

Now the asymptotic lower bound is the best case at which the fake coin can be detected, it cabe detected in first weighting itself when “n” is odd and the weights shows same weight after weighting it after removing a coin, the removed coin will be the fake coin.

Thus Asymptotic lower bound will be = Ω(1)

Decision tree can be depicted as given below, in which the first weight can also detect the fake coin if luck is there, so the asymptotic lower bound is : Ω(1)