I grant readers of this page the right to reproduce one copy of any paper on this page for the purposes of research and self-study.
Waterloo undergraduate Ray Kuo made the following nice graphic illustrating my
hypothetical Canadian 83-cent coin, with the University of Waterloo's Math and
Computer Building on one side. It's reproduced here with his permission.
Several people wanted more details about the optimal systems
for Canada. Here's what I've computed. For amounts up to $5.00, Canadians
use the following denominations: 1 cent, 5 cents, 10 cents, 25 cents,
100 cents, 200 cents.
The expected number of coins per transaction is 5.9. The optimal 4-coin
system is (1,7,57,80), with an expected 6.804 coins per transaction.
The optimal 5-coin system is (1,6,20,85,121) with an expected 5.44 coins
per transaction. The optimal 6-coin systems are (1,6,14,62,99,140)
and (1,8,13,69,110,160), each of which give an expected 4.67 coins per
transaction.
For the greedy algorithm, I obtained the following results. The optimal 4-coin systems are (1,5,23,109) and (1,5,23,110), with an expected 7.176 coins per transaction (as compared to 5.9 with the current 6-coin system). The optimal 5-coin systems are (1,4,13,44,147), (1,4,13,44,150), (1,4,14,47,160), and (1,4,14,48,160) with an expected cost of 5.816 coins per transaction. The optimal 6-coin systems are (1,3,8,26,64,{202 or 203 or 204}) and (1,3,10,25,79,{195 or 196 or 197}) with an expected cost of 5.036 coins per transaction.
Note added October 23, 2003: Both Europe and China use a system of denominations based on the recurring pattern
1,2,5, 10,20,50, 100,200,500, ...This may seem natural, but a small change to
1,3,4, 10,30,40, 100,300,400, ...would significantly decrease the average number of coins per transaction. This new system has the following advantages:
