Classifying Five Bags of Coins With a Single Weighing

Worked Solution

How to Think About It: There are $3^5 = 243$ possible assignments of types to bags, and one weighing yields one real number. If we can make every assignment produce a different number, one weighing suffices; since zero weighings obviously cannot, the answer is one. The design problem is to pick coin counts $c_1, \ldots, c_5$ such that the map from deviation vectors $(d_1, \ldots, d_5) \in \{-1, 0, 1\}^5$ to $\sum_i c_i d_i$ is injective.

Quick Estimate: With counts $1, 3, 9, 27, 81$ the deviation $\sum c_i d_i$ ranges from $-121$ to $+121$, which is exactly $243$ integers, one per configuration. That is the tightest possible fit, so the encoding is perfectly efficient.

Formal Solution:

*Step 1 -- Lower bound.* Zero weighings give no information and there are 243 possibilities, so at least one weighing is required.

*Step 2 -- The sample.* Take $1$ coin from bag $1$, $3$ coins from bag $2$, $9$ from bag $3$, $27$ from bag $4$ and $81$ from bag $5$, for $121$ coins in total. Let $d_i \in \{-1, 0, +1\}$ be the per-coin deviation of bag $i$ from $10$ g (so $d_i = -1$ means 9 g coins, $d_i = +1$ means 11 g coins).

*Step 3 -- The reading.* The scale shows $$W = 10 \times 121 + \sum_{i=1}^{5} 3^{\,i-1} d_i = 1210 + D, \qquad D = d_1 + 3 d_2 + 9 d_3 + 27 d_4 + 81 d_5 .$$

*Step 4 -- Uniqueness of decoding.* $D$ is a balanced ternary numeral with digits $d_i \in \{-1, 0, 1\}$. Balanced ternary representations are unique: if two different digit vectors gave the same $D$, subtracting would give $\sum 3^{i-1} e_i = 0$ with $e_i \in \{-2, -1, 0, 1, 2\}$ not all zero; taking the smallest $j$ with $e_j \ne 0$, the sum equals $3^{j-1}(e_j + 3 \cdot \text{integer})$, and $e_j + 3k = 0$ is impossible for $e_j \in \{\pm 1, \pm 2\}$. So the $243$ configurations produce $243$ distinct values of $D$, namely every integer from $-121$ to $121$.

*Step 5 -- Decoding procedure.* Compute $D = W - 1210$. Then read off the digits from the least significant: $d_1 \equiv D \pmod 3$ interpreted in $\{-1, 0, 1\}$ (residue $2$ means $-1$); replace $D$ by $(D - d_1)/3$ and repeat for $d_2$, and so on up to $d_5$. Bag $i$ is light, genuine, or heavy according to $d_i = -1, 0, +1$.

*Step 6 -- Example.* A reading of $W = 1196$ gives $D = -14$. Then $-14 \equiv 1 \pmod 3$, so $d_1 = 1$ and $D \to (-14 - 1)/3 = -5$; $-5 \equiv 1$, so $d_2 = 1$ and $D \to -2$; $-2 \equiv 1$, so $d_3 = 1$ and $D \to -1$; $d_4 = -1$ and $D \to 0$; $d_5 = 0$. Check: $1 + 3 + 9 - 27 + 0 = -14$. So bags 1, 2, 3 hold 11 g coins, bag 4 holds 9 g coins, bag 5 is genuine.

Answer: (a) One weighing suffices (and is obviously necessary). (b) Take $1, 3, 9, 27, 81$ coins from bags $1$ to $5$ (121 coins), weigh them, and set $D = W - 1210$. Writing $D$ in balanced ternary, $D = d_1 + 3 d_2 + 9 d_3 + 27 d_4 + 81 d_5$ with $d_i \in \{-1, 0, 1\}$, gives the type of each bag: $d_i = -1$ means 9 g, $0$ means 10 g, $+1$ means 11 g.