One heavy coin in twenty-seven
You have coins that look the same. All have the same weight except one, which is slightly heavier. You have a two-pan balance with no weights; each weighing tells you which side is heavier, or that they balance.
What is the smallest number of weighings that is always enough to find the heavy coin?
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
A weighing has three possible outcomes, not two. How many coins can you handle with one weighing?
Split the coins into three equal groups.
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. Each weighing gives one of three answers, so weighings can tell apart at most cases. A three-way split reaches that bound.
Lower bound. There are possible heavy coins. After weighings there are at most different sequences of outcomes, and each sequence must point to a single coin. So , that is .
A strategy with weighings.
- Split the coins into three groups of and weigh two of them. If one side is heavier, the coin is there; if they balance, it is in the third group. Now candidates remain.
- Split the into three groups of and do the same. Now candidates remain.
- Weigh one candidate against another. The heavier one is the coin; if they balance, it is the third.
So the answer is .
The lesson. Design each measurement so that its outcomes are as equally likely as possible. Weighing against would be a poor first move: it isolates the heavy coin only if the scales balance, which happens with probability .