Suppose there are seven coins, all with the same weight, and a counterfeit coin that weighs less than the others. how many weighings are necessary using a balance scale to determine which of the eight coins is the counterfeit one? give an algorithm for finding this counterfeit coin.
Answers
Answered by
0
I would weigh 7 out of the 8 coins. That way I will not necessarily have to weigh all of the coins, but if it is not one of the 7 that were already measured, then I would know for a fact that the counterfeit coin would be the "last one", or 'the odd one out'.
Answered by
0
Answer:
There are three possibilities for each weighing on a balance scale.
Step-by-step explanation:
The two pans can have equal weight, the first pan can be heavier, or
the second pan can be heavier.
Consequently, the decision tree for the sequence of weighings is a
3-ary tree.
There are at least eight leaves in the decision tree because there are
eight possible outcomes.
It follows that the height of the decision tree is at least log3 8e = 2.
Hence, at least two weighings are needed.
Similar questions