# How can I assign weights to coins so that they can be counted in a single weighing?

I was sorting out the coins in my loose-change jar the other day, and the following thought crossed my head: Is it possible to deduce the number of each type of coin in this pile by simply weighing them?

The coins I were counting were Australian 5c, 10c, 20c and 50c. According to Wikipedia, they weights are:

5c     2.83 grams
10c    5.65 grams
20c   11.30 grams
50c   15.55 grams

But this might be a particularly bad choice of weights for the coins. Since 565 divides 1130, we can't tell the difference (through weighing) between two 10c coins and one 20c coin. It seems that two 5c coins and one 10c coin would be hard to distinguish also.

So my question is:

Question: What would be a better way to designate the weights of these coins so that we could (in most cases) uniquely determine the number of each type of coin in a single weighing?

This would be subject to some practical constraints:

• Each coin is a reasonably light, but not too light (e.g. between 2 and 20 grams).
• If A and B are two multisets of coins, and A and B have equal weights, then |A| and |B| should be very large (more than is likely to be in a typical jar).
• The scales do not measure with infinite precision. Coins are not minted with infinitely accurate weights.
• The weights of the coins must differ by a reasonable amount (e.g. by at least 3 grams).
-
Multiply all your weights by 100 to make them whole. Now you probably want all the weights to be pairwise relatively prime and "big". If you had infinite precision, you should take all weights rationally independent, but I guess you already knew that... –  Yuval Filmus Dec 20 '10 at 23:17
That'd be my natural reaction. However, I'm wondering if there's something I'm missing... e.g. some real-world constraint. –  Douglas S. Stones Dec 20 '10 at 23:27
As you say, each coin comes with an error bound on its weight. I don't know what a reasonable bound is, but I suspect they will quickly overlap. The nice thing about the weights of the 10c and 20c coins is that although you don't know how many you have, you do know the total value. Maybe that is more important. –  Ross Millikan Dec 21 '10 at 0:30
Would you happen to know the weight tolerances imposed for each denomination by the Australian mint? –  Ｊ. Ｍ. Dec 21 '10 at 5:14

A small observation. For two coins let's suppose we arbitrarily fix the precision at somewhat better than one gram, so let's make the weights $w_1, w_2$ positive integers. Then the way to minimize redundancy is to require that the weights $w_1, w_2$ are relatively prime. This is to maximize the size of the smallest nontrivial solution to $w_1 x + w_2 y = 0$. Within the constraints you describe this means we should take $w_1 = 17, w_2 = 20$; then we can decide the number of coins unambiguously up to the point where we have either $20$ of the first coin or $17$ of the second.
If we up the precision to somewhat better than a tenth of a gram then we should instead take something like $w_1 = 16.9, w_2 = 20$; then I think we can decide the number of coins unambiguously up to the point where we have either $200$ of the first coin or $169$ of the second, which is surely good enough for all practical purposes. So it seems to me that the answer to the problem depends strongly on what precision we can measure weights to.