You have n coins | they all look identical, and all have the same weight except

Question

You have n coins | they all look identical, and all have the
same weight except one, which is heavier than all the rest. You also have a balance scale, on which
you can place one set of coins on one side, and another set of coins on the other, and the scale will
tell you whether the two sets have the same weight, and if not, which is the heavier set. Assume
that n is a power of 3.

Q)Show that any strategy that correctly identies the heavy coin must use at least log3 n weigh-
ings in the worst case.

Explanation / Answer

since the balance provides us three cases and we have n coins so 1/3rd of n coins weighed at a time and this is repeated x times to arrive at conclusion then n*(1/3)*(1/3)*(1/3)*.... x times = 1 n(1/3^x) = 1 n = 3^x x =log3 n

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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