Are we really making the right coins from a mathematical point of view? Is a penny,a nickel, a dime a quarter and 1,5,10,20,50 and 100 dollars bills the optimal configuration? Or is there a better configuration that can be more useful? What do you think. I came up with this question because I was thinking about the metric system and how it was a lot more intuitive and I wondered if the same was true about currency.
How to divide currency?
-
5The word "optimal" only makes sense if there is a cost function to be minimized, or an utility function to be maximized. You gave us neither cost nor utility. – 2012-09-22
-
1The standard monetary series $1,2,5,10,20,50,\dots$ is a compromise between several goals: (1) it should contain the powers of 10, (2) there should be an approximately constant factor between the different values, (3) that approximate constant shouldn't be too large. – 2012-09-22
-
0No, it could be more optimal if there was a half-dollar coin. But wait, there is one: http://en.wikipedia.org/wiki/Half_dollar_(United_States_coin) – 2012-09-22
-
0But half dollar bills arent common. – 2012-09-22
-
0I remember this was asked here, but sadly I don't have the time to look for it. – 2012-09-22
-
1I haven't seen a fifty-cent coin in a long time, and I think some people disliked them when they were not unusual. I suspect they're no longer made. Two-dollar bills are famous for inciting suspicions and in recent years are very rarely seen. I don't know if those are currently made. I have one. – 2012-09-22
-
0@MichaelHardy: I've never met anyone who was suspicious about two-dollar bills. They dropped out of use, though, after the two-dollar coin was introduced in 1996. – 2012-09-22
-
0I had no idea there was a two-dollar coin. – 2012-09-22
-
0There is in Canada. – 2012-09-22
3 Answers
As others have said, it depends on how you define “optimal”.
I'm going to assume you asked: “What set of coin denominations minimizes the number of coins required in a cash transaction, assuming that all 100 possible values for the dimes/cents places are equally likely?” (This assumption isn't quite true in reality because of things like vending machines that don't accept pennies. There's also 99¢ psychological pricing, but sales tax tends to cancel that out.)
I shall further assume that you will use the greedy algorithm for change-making.
def num_coins(amount, denominations): result = 0 for coin in sorted(denominations, reverse=True): result += amount // coin amount %= coin if amount != 0: raise ValueError('Cannot make change for amount with the given coins') return result
The average number of coins per transaction can then be calculated as:
def avg_num_coins(denominations): return sum(num_coins(amount, denominations) for amount in range(100)) / 100.0
Applying this to the {1, 5, 10, 25} set of US coin denominations gives an average of 4.7 coins per transaction (2 pennies + 0.4 nickel + 0.8 dime + 1.5 quarters).
What's the optimum?
Trivally, 1.0. Have 99 different denominations of coins, from 1¢ to 99¢. However, this would make cash registers quite unwieldy. So, a better question would be, what's the optimum given a constraint on the number of coin denominations in circulation?
With 1 denomination
In order to be able to make any amount 1¢ or higher, the smallest coin has to be 1¢.
With a penny-only denomination system, the average number of coins per transaction is 49.5. Obviously not very efficient.
With 2 denominations
Find x such that avg_num_coins({1, x})
is minimized. This can easily be obtained by brute force, trying all values of x between 2 and 99. I got two optimum solutions, both of which result in an average of 9 coins per transaction:
- 1¢ and 10¢
- 1¢ and 11¢
Of these, we would probably prefer to use 10¢ coins rather than 11¢ coins, for ease of arithmetic.
With 3 denominations
Two combinations of denominations give the minimum of 5.26 coins per transaction:
- 1, 5, and 22¢
- 1, 5, and 23¢
Constrained to factors of 100
If you're willing to tolerate the inefficiency of 5.5 coins instead of 5.26, you could instead have one of the following:
- 1, 4, and 20¢
- 1, 5, and 20¢
- 1, 5, and 25¢
With 4 denominations
Our {1, 5, 10, 25} system with an average of 4.7 coins per transaction is, in fact, not optimum. We could instead use one of the following sets of denominations with an average of only 4.1 coins per transaction:
- 1, 3, 11, and 37¢
- 1, 3, 11, and 38¢
Constrained to factors of 100
Unfortunately, the above systems make it hard to make change for a dollar. Instead of a nice easy 2 half-dollars, 4 quarters, or 5 20-cent coins, you'd have to break a dollar into 37 + 37 + 11 + 11 + 3 + 1 or 38 + 38 + 11 + 11 + 1 + 1.
An alternative with an average of 4.6 coins per transaction (slightly better than the status quo) would be to have a {1, 4, 10, 25} system (i.e., replace the nickel with a 4¢ piece).
With 5 denominations
An average of 3.46 coins per transaction can be obtained with any of the combinations:
- 1, 3, 7, 16, 40¢
- 1, 3, 7, 16, 41¢
- 1, 3, 7, 18, 44¢
- 1, 3, 7, 18, 45¢
- 1, 3, 8, 20, 44¢
- 1, 3, 8, 20, 45¢
Constrained to factors of 100
An average of 3.76 coins per transaction can be obtained with the set {1, 4, 10, 25, 50}.
With 6 denominations
An average of 3.13 coins per transaction can be obtained with any of:
- 1, 2, 5, 11, 25, 62¢
- 1, 2, 5, 11, 25, 63¢
- 1, 2, 5, 13, 29, 64¢
- 1, 2, 5, 13, 29, 65¢
Constrained to factors of 100
An average of 3.36 coins per transaction can be obtained with the set {1, 2, 4, 10, 25, 50}.
The Euro cent denominations of {1, 2, 5, 10, 20, 50} just barely misses optimality, with 3.4 coins per transaction.
In general
A set of denominations is “optimal” if it makes the ratios between consecutive denominations as equal as possible. For example, the {1, 5, 22} set has the ratios 5¢/1¢ = 5, 22¢/5¢ = 4.4, and $1/22¢ = 4.545454... This can be seen as an integer approximation to {1, 100^(1/3), 100^(2/3)} = {1, 4.641588833612778, 21.544346900318832}.
Real-life currencies sacrifice “optimality” in order to make the denominations nice round numbers in base ten. Effectively, this constrains ratios between denominations to the set {2, 2.5, 4, 5}.
The set of US coin denominations are suboptimal because of uneven spacing: In particular, there's a ratio of 5 between the penny and the nickel, but only 2 between the nickel and the dime.
Open Questions
Banknotes
The analysis above assume a uniform distribution of the dimes+cents digits of prices. But this wouldn't work for larger denominations: I'm far more likely to spend a fiver than a Ben. Would an exponential distribution work better?
Non-decimal currency
Did Jefferson make a mistake when he argued for 100 cents in a dollar? Would it have been “better” better to use the old British £sd system with 240 pence to a pound? Adopt base-twelve system with 144 pennies to a dollar? Or stuck with the historical binary divisions (1/2, 1/4, 1/8, 1/16, etc.) of a dollar, like the NYSE did until 2001?
-
1Suppose you only have 2 and 3 cent coins, then you can have 1 cent net exchanges. – 2012-09-22
-
1@akkkk: True, but then the "greedy" algorithm wouldn't work, among other disadvantages. – 2012-09-22
One nice property about our currency is that it possesses optimal substructure with regard to making change. That is, if you want to give someone, say, $0.57 using the fewest coins, you can do so by always giving the largest possible coin at each step. In this example, two quarters, a nickel, and two dimes.
Not all denominations have this property. For example, suppose our coins were only four-cents and five-cents. It is possible to make $0.08, but the greedy algorithm of "always give the largest coin" would mislead you.
-
1Ok so dollars have optimal substructure. So does that mean they are the best we can do? Are all systems with this property as good? – 2012-09-22
-
0That depends on what you think makes one currency better than another. I simply wanted to point out a desirable property of the one you mentioned. – 2012-09-22
-
1For a real-life example of non-optimal substructure: The old British "florin" and "half-crown" coins were in a 4:5 ratio. – 2012-09-22
Let $\mathcal{B} := \{1,5,10,20,50,100,1000\}$ be a set of bills. For every positive integer $n$ there exists a positive integer $m$ and bills $b_1, b_2, \dots, b_m \in \mathcal{B}$ such that
$$b_1 + b_2 + \dots + b_m = n$$
Of course, in general such a "decomposition" will not be unique. For example, if $n = 10$, we have three admissible decompositions:
- $m = 1$, $b_1 = 10$: we have the trivial case $10 = 10$. In other words, we can pay a 10 dollar bill with a 10 dollar bill.
- $m = 2$, $b_1 = b_2 = 5$: we have $10 = 5 + 5$, i.e., we can pay a 10 dollar bill with two 5 dollar bills.
- $m = 10$, $b_1 = \dots = b_{10} = 1$: we have $10 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1$, which is the same as saying that we can pay a 10 dollar bill with ten 1 dollar bills.
If there are several admissible decompositions, one can start talking about the optimal one. If your goal is to minimize the number of bills you hand to the cashier, then you choose the decomposition with $m = 1$ and pay a 10 dollar bill with one 10 dollar bill.
What you can do is invent several sets of bills, and then compute the average length of the decomposition when $n \in \{1,2,\dots,100\}$. Find out which set of bills yields the least average length.
-
0Having a bill for each natural number would be optimal in this sense (I can pay any amount with a single bill), but is certainly impractical. Without an explicit function to optimize, all we can do is guess about how many bills is too many. – 2012-09-22
-
0@AustinMohr: You're totally right, of course. The cost function should thus incorporate a term that penalizes large sets of bills. Something like $|\mathcal{B}|^2$ would work, I suppose. Or, alternatively, one should consider only sets of bills whose cardinality is, at most, $10$, for example. Printing a different bill for each integer would be too expensive. – 2012-09-22
-
0I don't think this is a very mathematical or enriching answer. – 2012-09-22
-
0@Auke: The question was not *mathematical* either, given the OP's lack of definition of "optimal". Garbage in, garbage out... – 2012-09-22
-
1@RodCarvalho: Sure enough, we as mathematicians can shed some light on various optimality conditions, and previous solutions to this problem. Repeating the problem statement in mathy words is not an answer at all. – 2012-09-22
-
1@Auke: Ill-posed problems cannot be answered mathematically, but one can point out why they're ill-posed and try to steer the OP towards well-posed problems. I suggested a cost function at least. You just whine. If you dislike my answer so much, just downvote it. – 2012-09-22