Yoak: Denominations of money
A friend posed this to me today:
Devise an alternate set of denominations for coins and bank notes requiring a minimum number of denominations and such that any amount from $0.01 to $100 could be paid with four units of currency.
I’ve looked at this from another perspective before after it was discussed on Freakonomics but that has to do with minimizing the average number of coins needed and doesn’t go too much into the math.
What’s remarkable is that my friend nearly instantly came to an upper bound that isn’t huge and after hours five of us have failed to improve upon it. I’ll avoid stating that bound here for now, but will come back and add it to the comments in a bit if there is no traction.
Another interesting tidbit is that unlike U.S. denominations where a greedy algorithm can verify a minimal number of units that are required (take as many of the largest as you can, then as many of the next largest, etc.) denominations where the denominations aren’t multiples of each other don’t allow this. Making 15 in 12-5-1 shouldn’t be 12-1-1-1 — it should be 5-5-5. Even doing verification requires dynamic programming solutions.
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com
Andy said,
July 18, 2012 at 2:23 pm
There is the sort of obvious solution:
$0.01, $0.02, $0.03, …, $0.09
$0.10, $0.20, $0.30, …, $0.90
$1, $2, $3, …, $9
$10, $20, $30, …, $90
jyoak said,
July 18, 2012 at 11:06 pm
Andy, that’s the answer my friend came up with almost right away, but none of us have thought of any good way to argue that is an optimal solution nor have we found any way to get better than that.
Stephen Morris said,
July 21, 2012 at 10:13 am
I can save two units.
In Andy’s solution we can make up to 9 with one single digit coin so we add coins separated by 10 to allow us to reach 99 in two coins. Next we add coins separated by 100 to get up to 999 with three coins. Finally adding coins separated by 1000 gets us up to 9999 (and we can also make 10,000 by 9000 + 1000 for example).
This can be optimised by noticing that we can make up to 18 from two single digit coins. So the double digit coins can start at 19 and continue 29, 39, 49, …, 99.
Now we can make up to 99+9 = 108 with two coins, an improvement on before. So we can make the gap between the next coins be 109, rather than 100. Also we can make 108+99=207 with three coins so we can start at 208. Our next coins are:
208, 208+109=317, 426, 535, 644, 753, 862, 971
We have saved one coin already, essentially we don’t need the 100 coin because we can get to 200 with three of the smaller coins.
Now we can make up to 971+99+9 = 1079 with three coins, so our next gap will be 1080. We can make up to 1079+971 = 2050 with four coins so we start at 2051. Our final coins are:
2051, 3131, 4211, 5291, 6371, 7451, 8531, 9611
Again we have saved a coin by being able to reach 2000 with the lower coins, so we don’t need the 1000 coin. We can make all values up to 9611+971+99+9 = 10,690 or $106.90.
So our 34 denominations are
1, 2, 3, 4, 5, 6, 7, 8, 9,
19, 29, 39, 49, 59, 69, 79, 89, 99,
208, 317, 426, 535, 644, 753, 862, 971,
2051, 3131, 4211, 5291, 6371, 7451, 8531, 9611
To find the right coins for a particular amount the ‘greedy’ algorithm Jeff described should work. Always take the highest value coin you can until you reach zero.
BTW to have at least 10,000 combinations of four coins you need at least 17 denominations, so this is a lower bound. Interesting that it is half the number you seem to need.
I tried different variations on this, for example add a 109 value coin which saves you a coin later on. But you always end up needing 34. Maybe there’s a better way I didn’t try, or maybe there’s a completely different approach. I can’t prove that 34 is minimal.
Stephen Morris said,
July 22, 2012 at 6:24 pm
I have another approach but it only seems to be more efficient for smaller targets. This time you can’t use the ‘greedy’ algorithm, however there is an algorithm to get the right coins for a particular price.
To take a very simple example suppose you want to reach all prices up to 24 cents with four coins. Have a go at finding the fewest denominations for yourself.
Using the original approach I would need five coins: e.g. 1,2,3,6,12 (thinking that 24 = 2x2x2x3, similar to 10,000 = 10x10x10x10, so we need units (1,2), 3’s, 6’s and 12’s). As before the ‘greedy’ algorithm of taking the highest denomination until we reach zero works.
A better answer uses just three denominations: 1, 5 and 6. Please check for yourselves. This time the greedy algorithm does not work. However there is another algorithm that does.
24 decimal is 44 in base 5. 1, 5 and 6 decimal are 01, 10 and 11 in base 5. So we are using every base 5 number, with up to two digits, which only uses 0 and 1. We get 00 for free, we don’t need to include a zero cent coin.
Let’s see how this works. Suppose we want to make 14 decimal which is 24 base 5. 24 = 11+11+01+01 base 5, or in decimal 14 = 6+6+1+1. Hopefully you can see that we can make any number up to 44 base 5 = 24 decimal in this way.
Unfortunately this gets less efficient as we choose higher targets.
If the target was 624 (5^4 -1) then we would need every four digit base 5 number using only 0 and 1 (apart from the number zero). That is fifteen denominations. Using the old method would need sixteen denominations. So we are slightly better but not much.
By the time you get to 10,000 the old method works better.
Andy said,
July 25, 2012 at 1:50 pm
Here is a set of 33 coins that works:
1, 2, 3, 4, 5, 6, 7, 8, 19, 29, 39, 48, 59, 69, 78, 88, 98, 208, 317, 426, 535, 644, 753, 862, 971, 2051, 3131, 4211, 5291, 6371, 7451, 8531, 9611
Andy said,
July 25, 2012 at 2:21 pm
I found this paper which describes this problem: http://www.cs.uwaterloo.ca/journals/JIS/VOL13/Challis/challis6.html
Stephen Morris said,
July 26, 2012 at 2:25 pm
Thanks Andy, that’s a great link.
Your solution with 33 seems quite similar to mine, with the 9 missed out and some other minor changes. I’m trying to check it but don’t want to write code, so perhaps you can help. How do you reach 9610?