Register to reply 
Combinatorics problem with coins 
Share this thread: 
#1
May1014, 10:45 AM

P: 18

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] + any one 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 


#2
May1014, 07:31 PM

Mentor
P: 11,589

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 69, 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 14 4 coins to pay 19 5 coins to pay 119 6 coins to pay 139 7 coins to pay 159 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. 


#3
May1114, 02:36 AM

P: 18

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^{0} and 2^{n}  1 using a combination of the first n1 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... 


#4
May1114, 05:51 AM

P: 907

Combinatorics problem with coins
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_{2}(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 


#5
May1114, 06:44 AM

P: 18

Very interesting, thank you!



#6
May1114, 11:03 AM

HW Helper
P: 2,263

125 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^{n}1 with binary coins but having all the coins is harder the more there are binary is inconvenient unless your progression is 128256512 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 125 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 125 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 


#7
May1214, 12:37 PM

P: 18

That's very interesting, thank you!



Register to reply 
Related Discussions  
Coins combinatorics problem  Precalculus Mathematics Homework  6  
Coins in a box: aa conditional probability problem  Set Theory, Logic, Probability, Statistics  2  
Bayes Theorem for coins problem  Precalculus Mathematics Homework  1  
Coins problem  General Math  3  
Coins problem  General Math  2 