Five bags each hold many coins. Every bag is either all genuine at 10 g per coin or all counterfeit at 9 g per coin, and any number of the five bags, from none to all, may be counterfeit. Using one reading on a digital scale, identify exactly which bags are counterfeit.

Five bags each hold many coins. Every bag is either all genuine at 10 g per coin or all counterfeit at 9 g per coin, and any number of the five bags, from none to all, may be counterfeit. Using one reading on a digital scale, identify exactly which bags are counterfeit.

Approach: Take a different number of coins from each bag so that the total shortfall in grams identifies the offending set uniquely, then check the count of possible readings against the count of possible cases.

Take 1, 2, 4, 8 and 16 coins from bags 1 through 5 and put them on the scale together. If every coin were genuine the single weighing would read 10 * 31, or 310 g, and each counterfeit bag removes 1 g for every coin drawn from it, so the shortfall in grams is the sum of the powers of 2 belonging to the counterfeit bags. Binary encoding gives a unique representation of every integer from 0 to 31, so the shortfall names the guilty set exactly: a shortfall of 21, which is 16 + 4 + 1, means bags 5, 3 and 1, and a shortfall of 0 means all bags are genuine. The 32 possible readings match the 2^5 possible cases exactly. Drawing 1, 2, 3, 4 and 5 coins fails, since a shortfall of 5 could be bag 5 alone or bags 1 and 4 together.

Follow-up: How many bags can one weighing resolve if a bag may instead be genuine, 1 g light, or 1 g heavy?

Key concepts: binary encoding, unique representation, single weighing.