How to divide currency? 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.
 A: 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.
A: 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.
