Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).
share|improve this question
2  
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
2  
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? –  J. M. Dec 21 '10 at 5:14
add comment

1 Answer 1

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.