It has the charm of old scale problems: few movements, very expensive information and a solution that must be clean from the beginning. It does not ask for brute force, but for a good distribution of uncertainty.
The wise men and the pearls (ancient Persia)
Riddle statement
A sultan has 9 apparently identical pearls, but one weighs a little more than the others.
He has a two-pan scale and wants to identify the heaviest pearl using the smallest possible number of weighings.
What is the optimal strategy?
Show solution
Solution
Answer: The minimum is 2 weighings.
Explanation:
With a single weighing, a pan scale can only give three results: left heavier, right heavier or balance. This allows us to distinguish at most 3 cases, and here there are 9 possible pearls.
With two weighings you can distinguish up to
cases, just the necessary ones.
The specific strategy is to divide the 9 pearls into three groups of 3:
- Weigh 3 against 3.
- If they balance, the heavy pearl is in the remaining group; If not, it is on the saucer that goes down.
In the second weighing, you take the suspicious group and compare 1 against 1. If they tie, the third is the weighing; If not, the one that goes down is the one sought.