Brainteasers · Weighing and search · Easy
One heavy coin among twenty
Twenty coins look identical. Nineteen weigh exactly the same and one is slightly heavier. You have a balance with two pans and no weights: a weighing puts any coins you choose on each pan and tells you only which pan is heavier, or that the two balance. What is the smallest number of weighings that is certain to identify the heavy coin, however the weighings turn out?
Answer and solution
Answer
3
Solution
Each weighing has three outcomes, so it can cut the suspects to a third: w weighings handle up to 3ʷ coins.
Weigh 7 against 7 with 6 aside: the heavy coin is in the heavier pan, or aside if they balance, leaving at most 7 suspects. Weigh 2 against 2 with up to 3 aside, leaving at most 3. Weigh 1 against 1. That is 3 weighings. Two cannot be enough: two weighings have only 3 × 3 = 9 different outcomes, too few to point to one of 20 coins. The answer is 3.