Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
5  
The 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. –  Rod Carvalho Sep 22 '12 at 17:10
1  
The 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. –  celtschk Sep 22 '12 at 17:25
    
No, it could be more optimal if there was a half-dollar coin. But wait, there is one: en.wikipedia.org/wiki/Half_dollar_(United_States_coin) –  M Turgeon Sep 22 '12 at 17:29
    
But half dollar bills arent common. –  Bananarama Sep 22 '12 at 17:38
1  
I 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. –  Michael Hardy Sep 22 '12 at 18:48
show 4 more comments

3 Answers 3

up vote 5 down vote accepted

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?

share|improve this answer
1  
Suppose you only have 2 and 3 cent coins, then you can have 1 cent net exchanges. –  akkkk Sep 22 '12 at 19:50
1  
@akkkk: True, but then the "greedy" algorithm wouldn't work, among other disadvantages. –  Dan Sep 22 '12 at 21:08
add comment

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.

share|improve this answer
1  
Ok so dollars have optimal substructure. So does that mean they are the best we can do? Are all systems with this property as good? –  Bananarama Sep 22 '12 at 17:38
    
That 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. –  Austin Mohr Sep 22 '12 at 17:55
1  
For a real-life example of non-optimal substructure: The old British "florin" and "half-crown" coins were in a 4:5 ratio. –  Dan Sep 22 '12 at 17:59
add comment

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.

share|improve this answer
    
Having 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. –  Austin Mohr Sep 22 '12 at 18:05
    
@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. –  Rod Carvalho Sep 22 '12 at 18:10
    
I don't think this is a very mathematical or enriching answer. –  akkkk Sep 22 '12 at 19:49
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. –  akkkk Sep 22 '12 at 19:54
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. –  Rod Carvalho Sep 22 '12 at 19:58
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.