Lambdia

Ten Bags, One Reading: 55 Coins Turn the Dial Into a Label

Taking one coin from each bag reads 9.9 ounces whichever bag is light, and the failure is blindness rather than imprecision. Loading i coins from bag i makes the dial an injective function of the culprit, at a cost of the tenth triangular number. A 45-coin variant is cheaper, and powers of two identify any subset of light bags from one reading.

Ten bags of coins sit on a table. Every coin is supposed to weigh one ounce, but in exactly one bag every coin weighs 0.90.9 ounces instead. You have a scale that reports a number, not a balance that tips, and you may read it once. Which bag?

The instinct is to take one coin from each bag and weigh the ten together. That is a sound instinct about scales and a fatal one here, and it is worth being precise about why, because the failure is not a shortage of information.

The reflex reading contains no bag index

Nine honest coins and one light one weigh

9×1+1×0.9=9.9 oz9 \times 1 + 1 \times 0.9 = 9.9 \text{ oz}
(1)

and the striking thing about the right-hand side is what is missing from it. There is no kk anywhere. Whichever bag is the light one, the pile on the scale contains exactly one light coin, so the dial reads 9.99.9 in all ten cases. The scheme is not imprecise. It is blind, in the strict sense that the ten hypotheses produce the same observation.

What a single reading can do

A dial reports a real number, and the reals are infinite, so one reading can in principle separate any finite list of hypotheses. The constraint is never the count of weighings. It is whether the scheme makes the observation depend on the answer.

That reframing is the useful part, and it converts the puzzle into a design problem. Load the scale so that the reading is an injective function of the culprit.

Give each bag its own signature

Take one coin from bag one, two from bag two, and so on up to ten from bag ten. The number of coins on the scale is

1+2++10=10112=551 + 2 + \cdots + 10 = \frac{10 \cdot 11}{2} = 55
(2)

so if every coin were honest the dial would read 55.0055.00 ounces. Now suppose bag kk is the light one. Exactly kk of the coins on the scale came from it, each of them 0.10.1 ounces short, so

W(k)  =  (55k)1+k0.9  =  55k10W(k) \;=\; (55 - k)\cdot 1 + k \cdot 0.9 \;=\; 55 - \frac{k}{10}
(3)

The shortfall is k/10k/10, and reading it off is division. A dial showing 54.6054.60 is 0.400.40 ounces light, which at 0.10.1 ounces per light coin means four light coins, which means bag four.

Fig. 1 — The same ten hypotheses under the two schemes. Ten distinct readings, or one reading ten times over.

Injectivity is immediate from (3) and worth stating rather than assuming. If bags jj and kk were both consistent with the reading then

W(j)W(k)=kj10=0W(j) - W(k) = \frac{k - j}{10} = 0
(4)

which forces j=kj = k. The map is strictly decreasing, so no two culprits can share a dial position, and the ten readings run from 54.9054.90 down to 54.0054.00 in even steps of a tenth.

The general scheme, and a cheaper one

With nn bags the same construction puts

Tn=n(n+1)2T_n = \frac{n(n+1)}{2}
(5)

coins on the scale and produces nn readings Tnk/10T_n - k/10 spaced a tenth of an ounce apart. The triangular number is not a coincidence of the number ten; it is the price of using the coin count as a label.

Fig. 2 — Why the total is 55. Two copies of the staircase tile a 10 × 11 block, which is the standard picture behind equation (5).

Fifty-five coins is sufficient but not minimal, and the improvement is a one-character change. Draw 0,1,2,,90, 1, 2, \dots, 9 coins instead, which is 4545 coins and leaves bag one untouched. The honest reading is 45.0045.00, the light bag kk gives 45(k1)/1045 - (k-1)/10, and the case "dial reads exactly 45.0045.00" is itself informative: it means the untouched bag is the culprit. You are still separating ten hypotheses with one number, using ten fewer coins.

The scheme also generalises past the assumption that exactly one bag is light, which is the version I find more interesting. Draw 2i12^{\,i-1} coins from bag ii, for a total of 2101=10232^{10} - 1 = 1023 coins. Each light bag ii contributes a shortfall of 2i1/102^{\,i-1}/10 ounces, so

10×(shortfall)  =  iS2i110 \times (\text{shortfall}) \;=\; \sum_{i \in S} 2^{\,i-1}
(6)

and the left-hand side written in binary lists the light bags outright. One reading now identifies any subset SS of the ten bags rather than one bag out of ten, because binary representations are unique. The triangular scheme cannot do that: bags one and four together give the same shortfall as bags two and three.

What the idealisation is doing

Three assumptions carry real weight, and two of them are invisible in the statement.

The scale must resolve 0.10.1 ounces on a load of 5555, which is about 0.18%0.18\% precision. The powers-of-two version is worse: it needs a tenth of an ounce out of 10231023, roughly one part in ten thousand. This is where the puzzle stops being about combinatorics and starts being about instruments, and it is the honest reason a real counting house would weigh bags in pairs instead.

Bag ii must hold at least ii coins. The problem never says so, and the scheme quietly requires it. The 00 through 99 variant relaxes this by one coin per bag, which is another small argument in its favour.

And the light bag must be light coin by coin. A bag whose totalis ten percent short is a different problem entirely, because then a handful drawn out of it carries an unknown shortfall and equation (3) has nothing to stand on. Both readings of the phrase "this bag is ten percent light" sound the same out loud, and only one of them is solvable this way.

Why a pan balance would change the answer

Swap the dial for a two-pan balance and the whole analysis collapses, since a balance returns one of three symbols rather than a real number. Its information content per weighing is log231.585\log_2 3 \approx 1.585 bits, so ww weighings distinguish at most 3w3^w hypotheses. Ten bags need 3w103^w \ge 10, so w=3w = 3 would be the floor to beat, and the counting argument that makes a single reading obviously enough for a dial is exactly the one that makes it obviously not enough for a balance.

That contrast is the reason I like this problem. The instinct to weigh one coin from each bag is imported from the balance world, where symmetric loads are usually the right move. On a dial, symmetry is the enemy.

Sources and further reading

Every number above was checked before publication by symbolic algebra and by exhaustive enumeration of all ten culprits under both schemes, with a decoder given nothing but the dial reading. It recovered the right bag in every case, and the generalisation was rerun for every bag count from two to forty.

Comments · 0

Be the first to comment.