The Puzzle: You have 8 identical-looking coins. One is slightly heavier than the rest. You have a balance scale. What is the minimum number of weighings to find the fake coin?
1. The Strategy
Many people think it takes 3 weighings (binary search: 4 vs 4 -> 2 vs 2 -> 1 vs 1). But you can do it in 2 weighings by using the “Ternary” approach.
Weighing 1:
- Put 3 coins on the left and 3 coins on the right. (Keep 2 coins aside).
- Case 1 (Balanced): The fake coin is among the 2 you kept aside. Weigh those two against each other to find the heavy one. (Done in 2).
- Case 2 (Unbalanced): The fake coin is in the heavier group of 3.
Weighing 2 (For Case 2):
- Take the 3 heavy coins. Pick any 2 and put them on the scale.
- If one is heavier, you found it.
- If they are balanced, the 3rd coin (the one kept aside) is the fake one.
2. Conclusion
You can find the fake coin in a set of 8 (or even 9) in just 2 weighings.
Interview-Focused Questions
Q: Why is 3 vs 3 better than 4 vs 4?
A: Because with 3 vs 3, you create three groups (Left, Right, and Aside). A balance scale has three outcomes (Left heavy, Right heavy, Balanced). By matching the number of groups to the number of scale outcomes, you maximize the information gain per weighing.
Q: What if you had 12 coins and didn’t know if the fake was heavier or lighter?
A: This is a much harder version! Finding the fake coin AND its relative weight from 12 coins takes 3 weighings. It requires a complex swapping strategy.
Key Takeaway
Logarithms in base 2 (binary search) are common, but sometimes Logarithm in base 3 is the real secret to optimization.
Premium Content
Unlock Fake Coin and all premium lessons with a subscription.
From ₹199.99/year — See plans