Among 50 coins, exactly 1 coin is defective (heavier).
IBM aptitude question, verified with a worked answer. Free to practise - no sign-up.
Among 50 coins, exactly 1 coin is defective (heavier). What is the minimum number of weighings using a two-pan balance scale required to guarantee finding the defective coin?
Show answer & explanation
With a two-pan balance scale, each weighing can eliminate about 2/3 of the suspects (heavier side contains the defective coin). Starting with 50 coins: after weighing 1, at most ⌈50/3⌉ = 17 remain; after weighing 2, at most ⌈17/3⌉ = 6 remain; after weighing 3, at most ⌈6/3⌉ = 2 remain; after weighing 4, only 1 remains. Thus 4 weighings are necessary and sufficient.
Step-by-step Derivation:
Using information theory, each weighing gives a ternary result (left heavier, right heavier, or balanced). With n weighings, we can distinguish among 3^n outcomes. We need 3^n ≥ 50. Testing: 3^3 = 27 (insufficient), 3^4 = 81 (sufficient). Therefore, minimum n = 4. Verification via strategy: (1) Divide 50 into groups of 17, 17, 16; weigh two groups of 17—the heavier side has the coin. (2) Divide 17 into 6, 6, 5; weigh two groups of 6—the heavier side has the coin. (3) Divide 6 into 2, 2, 2; weigh two groups of 2—the heavier side has the coin. (4) Weigh the remaining 2 coins—the heavier one is defective.