Finding the Counterfeit Bag With One Weighing
There are 10 bags, each containing 100 coins. In 9 of the bags every coin is genuine and weighs exactly 10 grams. In the remaining bag every coin is counterfeit; all counterfeit coins in that bag have the same weight, which is either 9 grams or 11 grams (you do not know which). The bags look identical from the outside.
You have a digital scale that displays the exact weight of whatever is placed on it, but you may use it only once. Identify the counterfeit bag and determine whether its coins are light or heavy.
Hints
- With a single reading you need every possible answer (which bag, light or heavy) to produce a different number on the scale.
- Take a different number of coins from each bag, so that the deviation from the expected weight tells you which bag contributed it.
- Take 1 coin from bag 1, 2 from bag 2, ..., 10 from bag 10 (55 coins, nominal weight 550 g). The reading minus 550 equals plus or minus the counterfeit bag's number.
Worked Solution
How to Think About It: A single exact reading is one real number; you need an injective map from the 20 possible states (10 bags times light/heavy) into readings. Give each bag a distinct "signature" by taking a distinct number of coins from it.
Quick Estimate: If bag $k$ is counterfeit and you took $k$ coins from it, the total is off by $k$ grams, in the direction of the fake weight. Distinct $k$ means distinct deviations, so 1, 2, ..., 10 coins from bags 1 through 10 does it.
Formal Solution:
*Step 1 -- Construct the sample.* Number the bags $1$ to $10$ and take $i$ coins from bag $i$. The sample has $1 + 2 + \cdots + 10 = 55$ coins.
*Step 2 -- Nominal weight.* If all coins were genuine the scale would read $55 \times 10 = 550$ grams.
*Step 3 -- Read the deviation.* Let the reading be $W$ and let bag $k$ be the counterfeit bag with coins of weight $w \in \{9, 11\}$. The $k$ coins from bag $k$ each differ from $10$ g by $w - 10 = \pm 1$, so $$W - 550 = k \, (w - 10) = \pm k .$$
*Step 4 -- Decode.* $|W - 550| = k$ identifies the bag, and the sign tells you the type: $W < 550$ means the counterfeit coins weigh 9 g, $W > 550$ means 11 g. Every one of the 20 possible states maps to a distinct reading in $\{-10, \ldots, -1, 1, \ldots, 10\} + 550$, so the decoding is unambiguous.
*Step 5 -- Remark.* Taking $0, 1, \ldots, 9$ coins also works (45 coins, 450 g nominal), as long as the deviation $0$ is interpreted as "the bag with zero coins is counterfeit".
Answer: Take $i$ coins from bag $i$ for $i = 1, \ldots, 10$ (55 coins) and weigh them once. The reading minus $550$ g equals $+k$ or $-k$, where $k$ is the counterfeit bag and the sign tells you whether its coins weigh 11 g (positive) or 9 g (negative).
Intuition
One weighing gives you one number, so the design goal is to make that number a code. Taking $i$ coins from bag $i$ means the counterfeit bag shifts the total by exactly $\pm i$ grams, and since every bag has a distinct coin count, the shift identifies the bag while the sign identifies light versus heavy. This is the same encoding idea behind a single well-designed measurement that separates many hypotheses, and in research it is the habit of designing an experiment or a diagnostic trade so that each possible cause leaves a distinct fingerprint.