Problem #18 EASY
The Odd Ball Out
Apple Adobe Optimization Logic
Problem Statement
A jeweler has 9 gemstones that appear completely identical. One stone is a fake — it weighs slightly more than the genuine ones. You have a classic balance scale (no weights, no numbers). You want to find the heavier fake stone in as few comparisons as possible. How many weighings do you need, and what is your strategy?
Answer & Quick Explanation
Think you've got it? Click below to check your answer.
2 weighings. Divide 9 stones into three equal groups. Weigh two groups against each other to identify the guilty group of 3. One more weighing within that group pinpoints the heavier fake.
Detailed Editorial Solution
Want to see the step-by-step breakdown? Click below to reveal the editorial.
A balance scale returns one of three outcomes. With n weighings, you can distinguish up to 3^n cases. For 9 stones: 3^2 = 9, so 2 weighings suffice perfectly.
Step 1: Label the stones 1–9. Form three groups: A = {1,2,3}, B = {4,5,6}, C = {7,8,9}.
Step 2: Weighing 1: Place group A on the left pan and group B on the right pan.
Step 3: If the left side is heavier, the fake is in group A. If the right side is heavier, the fake is in group B. If the scale balances perfectly, the fake is in group C.
Step 4: You now know which group of 3 contains the fake stone. Pick any 2 stones from that group — one on each side of the scale.
Step 5: Weighing 2: If left is heavier, that stone is the fake. If right is heavier, that stone is the fake. If the scale balances, the third stone you set aside is the fake.
Step 6: Done in 2 weighings — optimal for 9 stones.
Key Insight:
Think in base-3. Each weighing gives 3 outcomes, so you can handle 3× more candidates per weighing than a binary approach. The reason 2 weighings work for 9 stones: 3^2 = 9 exactly covers the entire search space.