A Stack of Fake Coins

There are 10 stacks of 10 identical-looking coins. All of the coins in one of these stacks are counterfeit, and all the coins in the other stacks are genuine. Every genuine coin weighs 10 grams, and every fake weighs 11 grams. You have an analytical scale that can determine the exact weight of any number of coins. What is the minimum number of weighings needed to identify the stack with the fake coins?

Solution

References

B. Averbach and O. Chein, Problem Solving Through Recreational Mathematics, Dover, 2000, #9.11
A. Levitin and M. Levitin, Algorithmic Puzzles, Oxford University Press, 2011, #11

Solution

The puzzle can be solved in one weighing.

Number the coin stacks from 1 to 10. Take 1 coin from the first stack, 2 coins from the second, and so on, until all 10 coins are taken from the last stack. Weigh all these coins together. The difference between this weight and 550, the weight of (1 + 2 + ... + 10) = 55 genuine coins, indicates the number of the fake coins weighted, which is equal to the number of the stack with the fake coins. For example, if the selected coins weigh 553 grams, 3 coins are fake and hence it is the third stack that contains the fake coins.

Weighing Coins, Balls, What Not ...

72103978