4
$\begingroup$

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.

  • 0
    There is in Canada.2012-09-22

3 Answers 3

5

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?

  • 1
    @akkkk: True, bu$t$ then the "greedy" algorithm wouldn't work, among other disadvantages.2012-09-22
1

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.

  • 1
    For 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
0

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.

  • 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