How many weighings to find one heavy coin in 80?

Question

Among 80 coins, exactly one is heavier than the rest (which are all equal). You have a two-pan balance. What is the minimum number of weighings that guarantees you find the heavy coin, and how do you know fewer can't work?

Accepted Answer

Four weighings are necessary and sufficient. The information limit. Every weighing yields one of three outcomes (left down, right down, balanced), so k weighings produce at most 3^k distinct outcome-patterns. To identify 1 coin among 80 you need at least 3^k \ge 80. Since 3^3 = 27 < 80 and 3^4 = 81 \ge 80, you need 4 weighings. Three could distinguish only 27 cases, not enough for 80. Achieving 4 (split into three near-equal groups). Keep dividing the suspects into three groups as evenly as possible and weigh two of them against each other; the heavy coin's group is revealed (the heavier pan,…

How many weighings to find one heavy coin in 80?

Your answer

More Brainteasers questions