There is a very interesting article on this subject here: http://www.sciencenews.org/articles/20030510/mathtrek.asp.
The article makes a few interesting points. One is that the US coin system would become more efficient (in number of coins needed to provide transaction change) if an 18 cent piece were introduced to replace the dime. Keep the dime, and introduce a 32 cent coin for even greater transaction efficiency. ...though this is going to be harder for your high-school student clerks to add in their heads.
It also mentions that the "greedy algorithm" (starting from the largest denomination and working downward) provides the most efficient (in number of coins used) solution for US coin denominations, but isn't guaranteed to do so given the denominations of other countries.
| [reply] |
Says davido:
the US coin system would become more efficient (in number of coins needed to provide transaction change) if an 18 cent piece were introduced to replace the dime.
I looked into this in some detail eight or nine years ago. It turns out that there are two optimal systems, assuming that you want to have four coins. One system has a penny, a nickel, a quarter, and a glubbernog, which is worth 18 cents. With this system, you can expect to carry an average of only 3.88 coins at any time; the current system averages 4.69 coins.
The other optimal system replaces the quarter with a 29-cent snonkularb.
Among 5-coin systems, the optimal one has a penny, a nickel, and coins of denominations 16, 23, and 33 cents; under this system, you can expect to carry an average of only 3.28 coins at any time rather than 4.19 with the current system.
(Notice that 4.19 is exactly half a coin less than if you disregard half dollars; that's because half the time you are carrying at least two quarters and can replace them with a half dollar, saving one coin.)
The current system could be substantially improved by replacing the mostly-useless half dollar with a 32 or 33-cent coin; this would cut the average to 3.45 or 3.48 coins.
Of course, the real goal is to minimize weight and bulk, not number of coins. The obvious solution here is to make the quarters really small.
Hope this helps.
| [reply] |
| [reply] |
Says Eimi Metamorphoumai:
Interestingly, that only gives you the smallest number of coins for certain combinations of denominations.
I looked into this in some detail a while back also. As you point out, the greedy change algorithm for the US (1, 5, 10, 25) system always delivers the minimum possible number of coins for any amount, but this is a property of the particular denominations used. Clearly, a system with coins of size 1, 10, and 11 does not have this property, since the greedy algorithm gives change for 20 cents by starting with an 11-cent coin, and then delivers nine pennies.
When I realized this I started to look around to see if there were any widely-used coinage systems that did not have the greedy property. I was pleased to discover one: the pre-decimalization currency of the United Kingdom included the following coins:
half-crown = 30 pence
florin = 24 pence
shilling = 12 pence
sixpence = 6 pence
When changing four shillings = 48 pence, the greedy algorithm delivers a half-crown, a shilling, and a sixpence, but the optimal solution delivers two florins.
| [reply] |