Advanced fake-coin problem There are n 3 coins identical in appearance; either a

Question

Advanced fake-coin problem There are n 3 coins identical in appearance; either all are genuine or exactly one of them is fake. It is unknown whether the fake coin is lighter or heavier than the genuine one. You have a balance scale which you can compare any two sets of coins. That is, by tipping to the left, to the right, or staying even, the balance scale will tell whether the sets weigh the same or which of the sets is heavier than the other, but not by how much. The problem is to find whether all the coins are genuine and, if not, to find the fake coin and establish whether it is lighter or heavier than the genuine ones.

This is an unanswered book problem ( http://www.chegg.com/homework-help/introduction-to-the-design-and-analysis-of-algorithms-3rd-edition-chapter-11.2-problem-10e-solution-9780132316811 )

Explanation / Answer

it can be done by binary search. Let me take an example of 4 coins.

For this with 2 weighings we can find the defective coin.

Divide the coins into group of 2 and then weigh two coins on the weighing balance. If one side is heavy we know that the lighter side will have the defective coin.

In the next weighing weigh both the remaining coins and we will get the defective one.

Similar approach can be extended and use for more number of coins.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.