Some of the bags are fake, still one weighing

Question

You have ten large bags of coins. A genuine coin weighs exactly 10 grams; a fake weighs 11 grams. Each bag is either entirely genuine or entirely fake, and any number of the bags could be fake, from none of them to all ten. You have a digital scale that gives an exact reading, but you may use it only once. In the well-known version of this puzzle exactly one bag is fake and you take 1 coin from bag 1, 2 from bag 2, and so on. Here that no longer works: two fake bags could produce the same excess as a single different bag. How do you identify exactly which bags are fake with a single weighing?

Accepted Answer

Take 1 coin from bag 1, 2 from bag 2, 4 from bag 3, 8 from bag 4, and so on, doubling each time, up to 512 coins from bag 10. That is 1,023 coins in total. Put them all on the scale at once. Reading the result. If every coin were genuine the pile would weigh 10,230 grams. Each fake coin adds exactly 1 gram, so the number of grams above 10,230 equals the total number of fake coins on the scale. Because the counts are powers of two, that excess has exactly one way of being written as a sum of distinct powers of two. Write the excess in binary: every 1 bit points to a fake bag. Example. Suppose …

Some of the bags are fake, still one weighing

Your answer

Discussion

Learn the concepts

Related questions