2010- 2009
- 2008
- 2007
- 2006
- 2005
2004
Silence- Snowflakes
- Paranoia Pays
- Microsoft Help
- Polyglot 11: More C
- Polyglot 11: C
- Polyglot 10: Smalltalk
- Toronto Wisdom
- Exterminated
- The Last Straw
- BT Broadband Trap
- Polyglot 9: Moo
- Polyglot 8: SVG
- Polyglot 7: POV-Ray
- Polyglot 6: Python
- Polyglot 5: PHP
- Polyglot 4: Euphoria
- Polyglot 3: JavaScript
- Polyglot 2: Java
- Polyglot 1: VB
- POV-Ray
- Etch A Sketch
- Slashdotting
- Flashy Lies
- Scientific Illiteracy
- Creeping Featurism
- VidScope
- Saturn V
- Perspectives
- Slide Rule
- eBay Sale
- Iron Filings
- Gimble
- VBA Security
- Random Morsels
- Exact Change
- Easter Egg
- Diametral Pitch
- mod_deflete
- Ethical Spam?
- Deadlines
- CPU Power
- Fosdem 2004
- Academic Reversal
- Mars Memorial
- Culture Clash
- Watching the Users
- 2003
- 2002
Exact Change
17 April 2004
![[UK Tuppence]](/news/2004/coin.jpg)
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 two-week search using Python of all possible permutations turned up the following optimum sets:
| # | Coins | Average | Notes |
|---|---|---|---|
| 1 | [1] | 50.00 | The penny is required in any currency system to make exact change.[1] |
| 2 | [1, 10/11] | 9.09 | A clean logarithmic progression, either 10c or 11c will do. |
| 3 | [1, 12, 19] | 5.20 | Insane. |
| 4 | [1, 5, 18, 25/29] | 3.93 | Replace the dime with an 18c coin for greatest efficiency. Optionally also replace the quarter with a 29c coin (makes no difference). |
| 5 | [1, 5, 16, 23, 33] | 3.32 | Optimum 5 coin set. |
| 6 | [1, 4, 6, 21, 30, 37] | 2.95 | Optimum 6 coin set #1. |
| 6 | [1, 5, 8, 20, 31, 33] | 2.95 | Optimum 6 coin set #2. |
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:
| # | Coins | Average | Notes |
|---|---|---|---|
| 3 | [1, 5, 10, | 7.07 | Of North American coins, the quarter is most useful, and the nickel is least useful (the penny is manditory). |
| 3 | [1, 5, | 5.55 | |
| 3 | [1, | 5.45 | |
| 5 | [1, 5, 10, 25, 32] | 3.49 | Assuming the North American coins are fixed, a 32c coin would be the most useful addition. |
| 5 | [1, 2, 5, 10, 20, | 4.24 | Of European coins, the 2p, 5p, 20p, and 50p coins are all equally useful, and the 10p coin is least useful (the penny is manditory[1]). |
| 5 | [1, 2, 5, 10, | 4.24 | |
| 5 | [1, 2, 5, | 3.84 | |
| 5 | [1, 2, | 4.24 | |
| 5 | [1, | 4.24 | |
| 7 | [1, 2, 5, 10, 20, 33/37, 50] | 2.88 | Assuming the European coins are fixed, either a 33p coin or a 37p coin would be most useful. |
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.
