# 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.

-
In addition to this, remember that you can also perform a manual count of the number of coins. For example, if you have 5c coin weighing 10g, and 10c weighing 20g, then knowing how many coins there are. So 2 coins weighing 20g tells you that you have you have 2 5c coins. –  picakhu Dec 21 '10 at 3:54
At some point I had gathered about 1200 coins of 1NIS. These coins come in two different weights (at some point they changed the metallic composition of the coin). So no, 200 is not good enough for some practical purposes. –  Yuval Filmus Dec 21 '10 at 5:08

I am neither a mathematician nor particularly good at maths but here is my 'pennyworth' on the problem.

(1) Weighing the same denomination coins (assuming they are the same 'model') is extremely accurate with a reasonable digital scale. Once one is weighing upwards of twenty or thirty coins, the likely deviation from the true number of coins drops dramatically (thanks to the wonders of The Central Limit Theorem). I have used this approach to take inventories of paper work sets and I was surprised by just how accurate the item counts were using a cheap digital scale weighting up to 10 kilogrammes and with an accuracy of +/- one tenth of a gram. I had a weight to number conversion calculation in a spreadsheet but obviously a purpose-made scale 'would incorporate the conversion on a chip. There should be scope for 're-calibration' given that coins change.

(2) With a mixed bag of coins, it strikes me that no matter how cunningly one might design the coin weights, the more coins one had, the greater the number of possible weight combinations. At some point, these would 'eat into' the maximum accuracy range of the balance. If this is so (and this is only my intuition, this should be proven or disproven), then this would suggest a maximum number of coins that could be weighed at any one time. It could be objected that prime numbers solve this problem but if we think of the scale's accuracy as defining a minimum measurable number space, I suspect that populations of high primes or combinations with even relatively few primes could fall in the same number space and not be discriminated. Again, it would take a mathematician to show whether this intuition is grounded or foundless.

[P.S. Reading the foregoing posts more carefully, I see that Qiochu has already found the upper bound for a given set of weights]. This suggests another approach, namely, batching mixed coins into maximum number of coins or total weight and then weighing (and thus accurate counting) using Qiochu's system.

(3) One also should think of practicalities: (a) At the moment, coin weights are not designed for counting by weight. (b) Most people I have seen counting coins do so from a till in which the coins have already been sorted into denominations. This suggests that in the real world, the approach in the first paragraph is the best one.

(4) A fourth reflection is that with the advent of cash cards, 'money' cards, smart phone apps and other 'virtual purse' solutions, maybe the problem of counting coins is one that will not be with us for much longer. Perhaps coins could also be made another way, incorporating a passive (secure and non-rewritable!) RFID tag to 'tell' counting machines what denomination they are.

-
Welcome to our site! –  kjetil b halvorsen Jan 20 at 10:09