Recently Michael left the following challenge in a comment:
I’ve been trying to optimize my change-carrying habits. What is the smallest amount of quarters, dimes, nickels and pennies one can carry while still being able to give perfect change (two decimals)?
It’s not 100% clear what Michael meant by “give perfect change”, but let’s assume the goal is to be able to make any amount between 1 and 99 cents. For non-US readers, US coins are worth 1, 5, 10, and 25 cents.
Some questions for exploration:
- What’s the smallest number of coins you can come up with that works? What are they?
- Are there multiple solutions, or is the solution unique?
- How can you prove that a proposed solution is optimal? Unique?
- Can you answer the question for a different system of coins? For example, I am currently spending the summer in Cambridge, England, where coins are worth 1, 2, 5, 10, 20, and 50 pence. What if you also include the 1- and 2-pound (100 and 200 pence) coins, and want to be able to make change for every amount up to 5 pounds (the smallest note)?
- The US and UK coin systems both have the property that a greedy strategy works for giving the smallest amount of change. That is, to make a certain amount of change with the smallest possible number of coins, you can just keep picking the biggest coin less than or equal to the remaining amount. What about coin systems without this property? Do they make this problem harder? Easier?
- If you got to design your own system of coins with whatever denominations you wanted, how would you design it so that the minimum number of coins needed to make all amounts between 1 and 99 cents is as small as possible? As LARGE as possible?
- What are some methodologies for attacking this sort of question in general?
Feel free to come up with your own generalizations as well. Post questions, discussion, and solutions in the comments but don’t peek until you’ve tried solving it! I’ve posted another change-making puzzle before as well; the discussion there might also give you ideas.
The Math Less Traveled 
I’ve been wondering on and off about a different sort of optimal change carrying. What I want to do, hypothetically, is, given the change I have on me, know exactly what coins to give to the cashier (over the required amount) to minimize the total coins I will have after the transaction. For example, for any transaction for an odd number of cents, I should add a 1 cent coin, if I have any.
As best I can figure it, this means I will always have in the range of 0 to ceil((value of current coin) / (value of next coin up)) of each coin – preventing gradual accumulation of small coins.
1)
Just start at 1 and work your way up. This is ugly, but it works.
1-4 needs 4 pennies. It should be obvious this is all the pennies you will need. Also, it covers 80% of all the other values when we have values divisible by 5 worked out.
looking at minimum coinage/using what we already have:
5 -1n
10 – 1d
15 – 1d 1n
20 – 2d
25 – 2d 1n (we already had this!)
30 – 50 add 1q
55 – 75 add another q
80 – 100 add one more q
So the answer is 3q, 2d, 1n, 4 pennies = 10 coins or 104 cents. I’d throw in another quarter so you could buy a candy bar or a soda with your change.
2) You could switch out a coin and still have the full range. ie 3q, 1d, 2n, 4 pennies would still cover 1-99 and be 10 coins. SO you don’t have to give the optimum number of coins back to have an optimal # of coins in your pocket.
3)By brute force, this is optimal.
4)1, 2, 5, 10, 20, and 50 pence. What if you also include the 1- and 2-pound (100 and 200 pence) coins, and want to be able to make change for every amount up to 5 pounds.
This is a bit more interesting. since we are going from 1-499. Lets use the greedy algorithm to give the minimum number of coins back always.
this would leave us with 1-1, 2-2’s, 1-5, 1-10, 2-20’s, 1-50, 1-100, 2-200’s. 11-coins and covers .01-6.10. But, if you don’t have that much money you could switch out a 2 for a 1 lol, but there are no other switches possible. It is more efficient then US for 1-99 needing only 8 coins for 1-100.
5) The hard part (to me anyways) is designing a non greedy system, I can’t think of one right now! I cant even begin to answer the second part without an example.
6) The UK seems to to have it as small as possible. Large as possible would be a 1-cent piece and thats it!.
7) Seems a brute force type approach is the best possible because of the small space.
This might be interesting. Lets say you are making 2 purchases at different locations. What is optimal then?
What is the first store you don’t care about exact change and the second one you do (ie could possibly get change back) does that change anything at all?
Hey,
Yeah, that’s exactly what I meant. No matter the change, (e.g. 47 cents after the decimal), you can always give it. All the questions for exploration you gave were on my mind. 🙂
Cheers,
Michael
Pingback: Right answers for the wrong reasons « The Math Less Traveled
Hey, the coin problem given as far as being optimal is similar to another problem related to computer science in covering the full range of numbers in the most “efficient” manner possible and which base does this most effectively. Essentially one “coin” could be interpreted to be a digit in the system… this puts one restriction on the coin values being they have to be exponential i.e. (2, 4, 8, 16 etc…). The calculation of efficiency I think was based on the number represented compared to the number of digits required. Mainly considered was base 2 and then an interesting number system that was also considered during early phase of computer science. The balenced tertiary system. It was base three but the digits were still 1’s and 0’s except there was a “1” with a bar over it to mean subtract, essentially a negative indicator. If your not familiar with it check it out it would make a good article in and of itself to consider arithmetic with this system let alone it’s benefits compared to a standard base system we have currently.
Anyways, returning to the coin problem. A base 2 coin system easily answers the question of number for any denomination with proof guarenteed in the system itself. To represent 99 the sequence would go as follows “1100011” Thus meaning four coins to represent 99 and still have plenty of room up to 127. Compared to the system that requires ten coins and can only rep 104. This essentially provides the “extra quarter” for that candy bar.
Just read a little further in the blog to see a shout out to balanced tertiary.. sweet connection
I know this is old, but some questions still remain unanswered soo…
For (1) and (4) I just did what Josh did
As for (3) I have a little nigling feeling that there should be a more elegant method of proof than just brute force. But I honestly have no idea what form such a proof would take.
(5) fascinated me. It just seemed so common sense that any currency system should be greedy. But I soon figured that a non-greedy system was at least possible. Here’s one of the first I found: a currency with a 1, 4 and 6 unit system would not be greedy. Consider making 8 cents: a greedy approach would give 6,1,1, but the obviously simpler and non-greedy solution is 4 and 4. But does such a system make the problem dramatically more difficult? I don’t think so: What’s the most efficient system for making 1-20 cents in this situation? 3 1’s would be required to make 1, 2 and 3. We can now increase by 4’s, knowing that 1mod4, 2mod4 and 3mod4 will all be covered. An extra 4 will mean all numbers from 1 to 7 are covered, which means we can increase by 6 at a time: 3 6’s will take us past 20, so the most efficient system is 1,1,1,4,6,6,6 (or alternatively 1,1,1,1,4,6,6 or 1,1,1,4,4,6,6). Note that not every number can be made in the most efficient way (e.g. 8) but that is not required. If it were, I wonder how the problem would be influenced??? I think the general method of filling in all numbers beneath the next highest coin, and then adding the next coin until an even higher unit of currency is reached, is completely efficient in both greedy and non-greedy situations (though I offer no proof.)
(6) for this question, the solution: 1,2,4,8,16,32,64 requires just 7 coins, and covers every number up to 127 uniquely. 1,2,3,6,12,25,50 also requires just 7 coins. I don’t think an option with 6 or less is posisble, though, once again, no proof.
I just thought I’d post a generalized solution to the creating an efficient currency system problem. This algorithm will work for any currency base (not just 100), will create a system that requires the minimum number of coins to be carried, and gives YOU the freedom to choose round numbers as currency values.
Start off by writing all powers of two below your currency base in order. So, for a 100-based system we would write 1, 2, 4, 8, 16, 32, 64. Next, you would choose a currency value between half your base value and the highest power. For this example we would be picking something between 50 and 64. I’m going to choose 50. Our next choice will be between half of the previous choice and the next-highest power. In this case it would be 25-32. I like 30. Next we choose between 15 and 16 (I choose 15, half of 30), and after that we are forced to go with 8, 4, 2, and 1.
To recap, I’ve chosen 1, 2, 4, 8, 15, 30, and 50 as our new currency values. This combines the efficiency of the 1, 2, 4, 8, 16, 32, 64 system with the ease of calculation of our current system. Although if we really want to combine these two we should just switch to an octal number system.
Very cool! Why does this work?
Thank you! My system works because of the boundaries we set for each currency value.
The lower boundary makes sure that we will only need one of each coin. By dividing the previous value x by 2, we end up with values greater than x/2, x/4, x/8 … until we have 1. That way, all values lower than x can be made, because of the fact that n/2+n/4+n/8…=n.
The upper boundary (the powers of 2) makes sure that we only need the minimum number of coins. This is necessary because we can’t make coins less than half the value of the previous coin. If the minimum number of coins is 7 as in my example, using the powers of 2 ensures that the seventh and final coin we make will be worth 1 cent.
By having the minimum number of coins, and by using only one of each, we get the best possible system. (As a side note, these systems will always be greedy.) Hopefully that will explain it for you.
1) I originally solved this the same way as Josh, but then I found another solution:
There’s one important principle we need to remember in this: our coin collection needs to contain every combination of coins necessary to meet a value of x-1, with x being the value of each successively smaller coin. To start, since we’re dealing with values smaller than a dollar, we need to meet 100-1=99. To achieve that number, we can apply the greedy strategy, by dividing 99 by each successively smaller coin value and taking the remainder:
99/25 = 3, remainder 24. (We now have three quarters, which makes up $.75, leaving us with $.24 left to fill.)
24/10 = 2, remainder 4 (Now we have three quarters and two dimes, totaling $.95)
4/5 = 0, remainder 4 (We don’t need nickles to make $.99)
4/1 = 4 (Four pennies and we’re done.)
Now we need to repeat this step to ensure we can meet the value for 25-1=24, so we can meet the next smallest value below a quarter. Since 24 was our remainder after using three quarters previously, we know we’ve already met this requirement with two dimes and four pennies, so we can move on. Next we have to meet 10-1=9. We didn’t see this in our $.99 problem, so we’re going to have to add something. We start with the next largest denomination below a dime:
9/5 = 1, remainder 4 (We need one nickle.)
4/1 = 4 (We already have our four pennies.)
The last step is to meet 5-1=4, which we’ve already done with our 4 pennies. Interesting to find that the minimum number of coins to hit $.99 is only one coin away from the minimum to hit every number between $.01 and $.99!
And then after doing this, while writing my “proof” for why this works (if you can really call it a proof), I think I stumbled upon an even better, and (in my opinion) very elegant, solution:
In order to find the minimum number of coins to hit every combination from 1-99, you simply have to find the maximum number of coins that you can carry without hitting or exceeding the value of the next denomination up. 4 pennies doesn’t reach 5, one nickle doesn’t reach 10, two dimes doesn’t reach 25, and three quarters doesn’t reach 100; thus, that is the coinage you need to carry: four pennies, one nickle, two dimes, and three quarters, or ten coins.
2) This solution is unique. There is only one minimum number; any other combination besides this one would require more coins.
3) Why solution #1 works:
For any monetary system – or, for that matter, any numbering system – if you can achieve one less than all possible denominations, you can achieve all possible number combinations. I’ll use the decimal system as an example:
In the decimal system, let’s say we wanted the minimum number of possible digits to reach 99. Our “coins” in the decimal system consist of digit values: The smallest is 1, then the next is 10, then the next is 100. The formula above works here:
99/10 = 9 remainder 9
9/1 = 9
The minimum number of digits we need to go from 1 to 99 is 18: 9 digits in the ones place and 9 digits in the tens place. 0 doesn’t count as an actual digit here, but rather as a placeholder for the absence of a digit, just like 0 quarters doesn’t need to be represented physically. You could just as easily count them as -, 1, 2, 3, …, 1-, 11, 12, …, 2-, 21, 22, etc. Thus, with 18 digits (1-9 in the tens place and 1-9 in the ones place), you can reach all numbers ranging from 1-99. 0 in either place simply “doesn’t use” a digit, like handing in 0 pennies.
Essentially, if you look at the coin system as a numbering system, we have this:
{100} {25} {10} {5} {1}
In case it isn’t clear what I mean by that, I’ll write the same syntax for decimal and binary:
{10000} {1000} {100} {10} {1}
{16} {8} {4} {2} {1}
So if we look at this, what do we need to reach 99999 in decimal? We need the ability to reach 9999, 999, 99, and 9. And in order to reach 15 (01111) in binary? We have to be able to reach 7 (00111), 3 (00011), and 1 (00001). If we can’t reach all of those, we don’t have sufficient digits to express 01111. Translating that into the USD numbering system, in order to reach all combinations leading up to 99 (one less than a dollar, covering the quarter, dime, nickle, and penny places), we have to be able to reach all combinations leading up to 24 (one less than a quarter, covering dime, nickle, and penny), 9 (one less than a dime, covering nickle and penny), and 4 (one less than a nickle, covering penny). If we can reach all of those, then we have enough coins in each place to reach 99.
Why solution #2 works:
Continuing with the idea of looking at USD coins as a numbering system, we have to consider one of the attributes of a numbering system: the number in one position can never have a larger value than the smallest value of the lowest possible number in the next (larger) position. The ones place in decimal can never meet or exceed 10, for example, and the smallest place in binary can never meet or exceed 2 (binary 10). Thus, a numbering system based on USD would look like this:
[0-3] [0-2] [0-1] [0-4]
Why those numbers? 3 is the maximum number of quarters before hitting $1.00 (USD 10000), 2 is the maximum number of dimes before hitting $.25 (USD 1000), 1 is the maximum number of nickles before hitting $.10 (USD 100), and 4 is the maximum number of pennies before hitting $.05 (USD 10).
(Relating to Decimal: [0-9] [0-9] [0-9] [0-9]; to Binary: [0-1] [0-1] [0-1] [0-1]. 9 is the largest number before hitting 10, 1 is the largest number before hitting 2 (binary 10))
And $.99 would be represented as USD 3204; $1.00 as 3210. The largest number, 3214, would be $1.04. Expanding this to include bills, it would go on like this:
[0-∞] [0-1] [0-2] [0-1] [0-1] [0-4] [0-3] [0-2] [0-1] [0-4]$100 $50 $20 $10 $5 $1 $.25 $.10 $.05 $.01
$999.99 would then look like 9120143204. The largest number with the same number of digits, 9121143214, would represent a value of $1010.04. The next number up would be 10000000000.
4) Using the above formula and proof, this can solve the minimum number of “coins” necessary for any conceivable system of numbering.
5) I’m going to stick with Tom’s answer this one, I don’t really feel like doing it myself XD.
6) The smallest possible number of coins has been answered pretty comprehensively here. The LARGEST possible coin system depends on whether or not it’s allowed to go below a value of $.01. If not, then a system with only pennies would require you to carry 99 pennies. If so, then the number becomes infinitely larger as the value of the lowest denomination becomes infinitely smaller.
Looking at it as a number system, however, I would want to develop a system that accomplishes two things: 1) it uses exactly one coin of each denomination to reach all numbers from 1-99, and 2) one coin of each denomination reaches exactly 99. Tom’s system, 1,2,3,6,12,25,50, accomplishes this, which would enable $.99 in that coin system to be written as 1111111 and $1.00 to be written as 10000000. Of course, this holds absolutely no practical value, since no one would likely use that system for expressing price, but who said math has to be practical? 😛
7) I believe my second solution is the best strategy; look at the problem as a numbering system, determine the largest value of each position before hitting the next (larger) position, and carry that many coins.