Combinatorics problem with coins

[lavoisier]

I guess more and more people in the world tend to use virtual money (credit cards, direct debit cards...) to pay for their shopping.
Here in Europe, however, people often still use cash in many situations.
This obviously has a side effect concerning coins.

Except when you go to a bar, restaurant, etc, and round the sum to leave a tip, in all other cases you have to pay an exact amount of money, which is most often a decimal number.
So, if you pay the exact amount, or a whole number in excess of it plus the decimal part, you will get no small coins in return: at most pieces of 1.00 and 2.00.
But if you pay an amount corresponding to a whole number, you will most often get back small coins, i.e. pieces of 0.01, 0.02, 0.05, 0.10, 0.20 and 0.50.

Suppose you want to get rid of these small coins by spending them, but of course you don't want to carry a lot of weight around with you.

So here's the question: what is the smallest set of small coins (pieces of 1, 2, 5, 10, 20 and 50 cents) you need to have with you to be able to put together (once) any sum between 1 and 99 cents?

I thought this kind of problem had to do with the theory of Diophantine equations, but I wasn't sure how to set it up, so I just went by trial and error, and my solution seemed to be the following:

[1,2,5,10,20,50] + anyone of [1,10], [1,20], [2,10], [2,20]

I know that with these 8 coins one can indeed make any number between 1 and 99.
But is this the optimal solution? Or could one do this with even fewer coins?

L

 

[mfb]

You need 1 to pay 1, and you need at least two additional coins out of (1,2) to pay 4. That makes 3 coins with a maximum sum of 5. To pay 6-9, you need at least an additional coin out of (1,2,5) to get a maximal sum of 10. We can continue that way:
1 coin to pay 1
3 coins to pay 1-4
4 coins to pay 1-9
5 coins to pay 1-19
6 coins to pay 1-39
7 coins to pay 1-59
And then you certainly need an 8th coin to pay more than 59.

As we have an example of 8 coins, this minimum is the actual best thing you can do. Using different choices for the first step (pay 4) and the step before 50 (either 10 or 20 will work), I can confirm that you found all solutions with the minimal number of coins.

1,1,2,5,10,10,20,50 will have the minimal weight in most currencies.

 

[lavoisier]

Thank you for your reply, mfb.
Is there a branch of mathematics that deals with this kind of problems? Number theory?

I'm not sure why it was decided to have 1, 2 and 5 (and the same times 10) coins rather than any other combination. Perhaps it was down to ease of calculation...

If our coins were based, say, on the binary system, we could have pieces of 1, 2, 4, 8, 16, 32, 64, and in that case we would be able to make any sum between 2⁰ and 2ⁿ - 1 using a combination of the first n-1 coins, each taken at most once. So we would still need 7 coins to make all sums between 1 and 99 (or 128 in fact), and I suppose it would look much more complicated to calculate.
I wonder if there is any other system that would work more efficiently, or maybe there's a theoretical limitation to how small the set of coins can be...

 

[jbriggs444]

I wonder if there is any other system that would work more efficiently, or maybe there's a theoretical limitation to how small the set of coins can be...

If you have a set of n distinct coins, the number of subsets that can be selected numbers 2ⁿ. If some of the coins are indistinguishable (e.g. have the same denomination), the number of distinguishable subsets would be less than this.

So if you want to be able to come up with subsets of the coins in your pocket that add to n different totals then you need at least log₂(n) coins. For instance, to obtain each of 128 possible totals you will need at least 7 coins, no matter what denominations you are allowed to use.

For the case of wanting to make change for integer values 0 through n, the binary scheme always achieves this optimum.


The idea also sounds similar to the notion of radix economy except that your metric of goodness is based on radix minus 1 rather than radix. http://en.wikipedia.org/wiki/Radix_economy

 

[lavoisier]

Very interesting, thank you!

 

[lurflurf]

Is there a branch of mathematics that deals with this kind of problems?
I'm not sure why it was decided to have 1, 2 and 5 (and the same times 10) coins rather than any other combination.

If our coins were based, say, on the binary system, we could have pieces of 1, 2, 4, 8, 16, 32, 64, and in that case we would be able to make any sum between 2⁰ and 2ⁿ - 1 using a combination of the first n-1 coins, each taken at most once. So we would still need 7 coins to make all sums between 1 and 99 (or 128 in fact), and I suppose it would look much more complicated to calculate.
I wonder if there is any other system that would work more efficiently, or maybe there's a theoretical limitation to how small the set of coins can be...

Depending on what you mean by "this kind of problem" it could involve number theory, integer programing, or combinatorics among other areas.

1-2-5 was chosen for several reasons
-as stated above binary is optimal because using multiples of a coin is inefficient
you can only make n values with n of some coin, but you can make 2ⁿ-1 with binary coins
but having all the coins is harder the more there are
-binary is inconvenient unless your progression is 128-256-512
once you decide on a base of 100 you do not want binary coins
-binary requires 7 different coins
eight coin are only needed for 99 in 1-2-5
better to have six different coins and need to use eight rarely than needing seven different coins
in fact we only ever need to use six in 1-2-5 if we have 1,2,2,5,10,20,20,50 available, but we need eight ready
-we would like coins whose ratio is $\sqrt[3]{10}\sim 2.15443469$
since that number is not round we use 2,2 and 2.5 as approximate cube roots 10=2*2*2.5
1
2=2*1
5=2.5*2
10=2*5
20=10*2
50=2.5*20
100=2*50
continuing
200=2*100
500=2.5*200
1000=2*500
2000=2*1000
5000=2.5*2000
and so on

see here
http://en.wikipedia.org/wiki/Preferred_number
https://cs.uwaterloo.ca/~shallit/Papers/change2.pdf

 

[lavoisier]

That's very interesting, thank you!