Brainteasers · Weighing and search · Medium
Six sacks and one reading
Six sacks each hold a large number of coins. In each sack, either every coin is genuine and weighs exactly 10 grams, or every coin is fake and weighs exactly 11 grams. Any number of the sacks, from none to all six, may be sacks of fakes. You have a digital scale that shows the exact weight of whatever is put on it, and you may take one reading only, of a pile of coins that you choose from the sacks. What is the smallest total number of coins in a pile that is certain to tell you exactly which sacks hold fakes?
Answer and solution
Answer
63
Solution
The reading reveals the number of fake coins on the scale, so the counts taken from the sacks must have all their subset sums different: powers of 2.
With counts 1, 2, 4, 8, 16 and 32, the number of fake coins is a number from 0 to 63 whose binary digits name the fake sacks. That pile has 63 coins. Fewer cannot work: the 64 possible sets of fake sacks need 64 different counts of fake coins, each between 0 and the size of the pile, so the pile has at least 63 coins. The answer is 63.