
Exact Change17 April 2004 The monkeys who staff the cash registers at the local supermarket are rather hit and miss when it comes to figuring out what change to give. Despite the assistance of the cash register which computes the return value, they struggle to figure out which coins to use. Could a better set of coin values be made? Canada and the US both use four coins: 1c/5c/10c/25c. A Canadian 50c coin exists, but is never seen in circulation. I wrote a Python program to compute every transaction from 1c to 99c and compute the smallest number of coins each would require. The average transaction using North American coinage takes 4.75 coins. UK and Europe use six coins: 1p/2p/5p/10p/20p/50p. This logical progression continues with £1/£2/£5/£10/£20/£50. The same Python program computes that the average 1p to 99p transaction using UK coinage takes 3.43 coins. So the UK/European system is better? Not necessarily. Imagine a set of coinage that featured 99 coins. With that, the average transaction would take 1.00 coins. But it would be a royal pain to use. A twoweek search using Python of all possible permutations turned up the following optimum sets:
Initially I assumed that all the optimum sets would be evenly spaced on a logarithmic scale. But this clearly isn't the case. Maybe someone with greater mathematical aptitude can spot a pattern. Some other interesting sets are:
If you think that these "best solutions" would never be used because of the weird numbers, take a look at what the UK used to use before decimalisation: 4 farthings = 2 halfpennies = 1 penny, 12 pence = 1 shilling, 2 shillings = 1 florin, 5 shillings = 1 crown, 240 pence = 20 shillings = 1 pound (sovereign), 21 shillings = 1 guinea. I'd like to see today's supermarket staff deal with that. Postscript: Prior to undertaking this investigation I did quite a bit of Googling for prior research. Nothing turned up, mainly because there's no unique terminology to use. However, once I saw that North American currencies would benefit from an 18c coin, Google instantly returned this paper by Prof Shallit of the University of Waterloo. He ran the same computations and published exactly the same answers one year ago. Even Slashdot covered it. Oh well, at least there's now a completely independent implementation which confirms his results. ^{[1]} Technically, the penny is not mandatory in the European set if one relies on the change receiver to also give back change. E.g. 5p  (2p + 2p) = 1p. This technique is not possible in the North American set since all other coins are multiples of 5c. 