The teleporter misfires again and Kinesys appears in the courtyard of the Staterion Mint, just as the alarm goes off. Someone has slipped an entire stack of counterfeit coins into the vault.
The director, a Staterian with impeccable posture, explains that weighings are expensive: every use of the great official scale requires a permit signed in triplicate. “I’d like to do as few as possible,” she sighs.
Dord, who adores permits in triplicate, immediately volunteers to fill them out. Liz, more practical, walks over to the stacks of coins. Meanwhile M00N reassures the director: “Don’t worry, we’ll find the right stack. Maybe with just one weighing!”
The Riddle
There are ten stacks of ten coins each. One of the stacks is made entirely of counterfeit coins, but nobody knows which; however, you know the weight of a genuine coin, and you know that a counterfeit coin weighs one gram more than it should. The coins can be weighed on an ordinary scale (one that shows the weight). What is the minimum number of weighings needed to identify the counterfeit stack?
Hint
You don’t have to weigh whole stacks, or take the same number of coins from each stack. Look for a way to make the extra weight “tell” you which stack it came from.
Solution
The counterfeit stack can be identified with a single weighing.
Take one coin from the first stack, two from the second, three from the third, and so on, up to all ten coins from the last stack. Then weigh the whole collection of samples.
The excess weight, in grams, is the number of the counterfeit stack. For example, if the group of coins weighs seven grams more than it should, the counterfeit stack is the seventh one, from which seven coins were taken (each one gram too heavy).
The method would work even with an eleventh stack of ten coins: just take none from it, and zero excess weight would mean the counterfeit stack is that last one.