Money matters

I think we accept without questioning a lot of things. And some of these things are mostly worthless spending time on and therefore the acquiescence is justified. Now, just for the heck of it, I ask one such question.

First, the background. I have been travelling a bit recently and this has given me the opportunity to observe a few different currencies. They are nice mostly. The diversity is actually what makes it intriguing. For some people---the numismatists among us---it is intriguing enough to start a hobby. I have also indulged in some such acts : the American quarters, for example. There are quarters that have names of states (and other US territories I have come to learn) inscribed on them, and I have all of the 50 states except Michigan (If you have my evasive MI quarter, I can offer you a profit of 100% on it). The colours of the notes are actually nice, which is why I feel that the dollar is the dullest I have seen thus far. Colours, sizes, faces, watermarks, Braille symbols aside, what intrigued me was probably what is most to do with the currencies---the numbers. No, not the note numbers. The denominations.

Observation All currencies I have seen, have a subset of the following set as the denominations {0.01, 0.02, 0.05, 0.10, 0.20, 0.50, 1.00, 2.00, 5.00, 10.00, 20.00, 50.00, 100.00, 200.00, 500.00, 1000.00, ...}. You see a pattern here, that {1, 2, 5} play a key role and are repeated in all values---in ones, tens, hundreds etc.

Question There must be a reason for this pattern. If so, what? If not, why?

I now try to answer this question. I should at this point mention that I have done no research into this question. I have not attempted to look it up anywhere, not even a Google search. So, whatever follows, is what I think is most reasonable.

In trying to answer the question, I make a few assumptions and definitions that help me subsequently.

Assumption Everyone works in the decimal system. It seems to me that this assumption is logical. Even if it is disputed, the final answer here will have a counterpart that can be obtained with a similar analysis.

Definition Values are synonymous to decimal places. E.g. Units, Tens, Hundreds, Thousands etc.

Definition Practical values are those that would be useful. E.g. {Hundredths, Tenths, Ones, Tens, Hundreds, Thousands} are the practical values for many currencies. Some (like the South Korean dollar) might choose other practical values. This depends on the exchange rate / buying power of the currency.

Definition A denomination is called consistent if it repeats at every value. Thus, a currency denomination {0.01, 0.02, 0.05, 0.10, 0.20, 0.50, 1.00, 2.00, 5.00, 10.00, 20.00, 50.00, 100.00, 200.00, 500.00} is consistent, because the same denominations of {1, 2, 5} repeat at each value. We can denote a consistent denomination by simply specifying the denomination at ones value, and we call this set the basis of the denomination. For the above example, the basis is {1, 2, 5}.

Some currencies have slightly different denominations (like the 25 paise coins in India), but these exceptions are not consistent (i.e. they are not repeated in all values. e.g. you might find 25 paise coins, but not 2.50 rupee coins / notes, or 25 rupee notes). I will disregard such inconsistent denominations.

Assumption The choice of the denominations should be made keeping the convenience of the people using them in mind. Convenience will be qualified and quantified next.

Definition A consistent denomination is convenient if it allows for the paying of all practical numbers. That is to say that {2} is an inconvenient choice for the basis of a consistent denomination because you cannot make a payment of, e.g. 0.03 using this denomination.

The convenient denomination choice problem can be broken down to a similar, but simpler problem.

Lemma A consistent denomination is convenient if it allows every number from 1 through 9 to be payable through its basis.
Proof This is a straightforward claim, which I will explain through an example. Since we are using the decimal system, every practical number will consist of digits 0 through 9. All these numbers can therefore be split into different values, i.e. $245.86 can be split as $200 + $40 + $5 + $0.8 + $0.06. If all numbers from 1 through 9 are payable using the basis, any number at any other value will be payable through the basis at that value. Since $4 is payable using the basis, $40 will be payable using the corresponding denominations of Tens value etc.

The choice of a convenient, consistent denomination is thus reduced to the choice of a basis set that allows paying of all number from 1 to 9. We have thus far only qualified convenience. I now quantify it. For the purpose of illustration, we will assume, unless otherwise stated, that the basis is {1, 2, 5} since it is the most common basis. Strings of the basis are concatenations of the elements of the basis, e.g. 12 is a string. A string is a payment of a number if the sum of the symbols in the string is equal to that number, e.g. 12 is a payment of 3. I will assume that all permutations of the symbols in a string give the same string, so that the strings 12 and 21 are the same. The length of a payment is the number of symbols in it, e.g. the length of 12 is 2. For each number n from 1 to 9, let C(n) be the set of all payments of n. Here is an example of C(n) with the above basis.

C(1) = {1}
C(2) = {11, 2}
C(3) = {111, 12}
C(4) = {1111, 112, 22}
C(5) = {11111, 1112, 122, 5}
C(6) = {111111, 11112, 1122, 222, 15}
C(7) = {1111111, 111112, 11122, 1222, 115, 25}
C(8) = {11111111, 1111112, 111122, 11222, 2222, 1115, 125}
C(9) = {111111111, 11111112, 1111122, 111222, 12222, 11115, 1125, 225}

Let l(n) be the least length of the length of all payments in C(n). The following lists l(n) for the continuing example.

l(1) = 1
l(2) = 1
l(3) = 2
l(4) = 2
l(5) = 1
l(6) = 2
l(7) = 2
l(8) = 3
l(9) = 3

Let l(B) be the average of l(n) from 1 through 9 for the basis B. From the above, l({1, 2, 5}) = 17 / 9. In order for the comparison of l(B) between different bases B to be fair, we must consider different bases with the same cardinality. Let |B| = k. k = 3 for our example. Let l*(k) be the minimum of l(B) over all bases B of cardinality k, and let B*(k) be a basis (not necessarily unique) achieving this minimum.

Definition B*(k) is an optimally convenient consistent denomination of cardinality k.

Here's the rationale for this definition. With any basis B, l(n) denotes the least number of currency notes (or coins) necessary to make a payment of n. l(B) therefore is the average number of notes necessary to make a payment with the denomination being B, assuming that each number from 1 to 9 is equally likely (a reasonable assumption, I believe. Perhaps the tenths and the hundredths places might not satisfy this assumption, but let us disregard this). A denomination basis that minimizes this number is optimal in the sense of requiring the least number of notes for any transaction on an average, and therein lies the convenience of the chosen denomination.

Given this, it is natural to ask if {1, 2, 5}, the basis for the universal consistent denomination, is an optimally convenient consistent denomination. The problem of finding optimally convenient consistent denominations seems tough in general---it involves the "hard" problem of optimizing a set that will give the least average length of partitions of numbers based on that set. But for the case of the decimal number system, which we assume in our scenario, we can easily deduce a few results.

Claim B*(1) = {1} and l*(1) = 5.

In fact, {1} is the only convenient consistent denomination of cardinality 1. And in this case l(n) = n, and hence the claim is true. We note that 1 has to belong to every convenient consistent denomination.

Claim B*(9) = {1, 2, ..., 9} and l*(9) = 1.

Straightforward claim. Every number has a note so that l(n) = 1 for all n.

Claim l*(k) is non-increasing in k.
Proof Let m be a number from 1 to 9 not contained in B*(k). Let B' be the union of B*(k) and {m}. Then l*(k + 1) is not larger than l(B'), by definition. Further, l(B') is not larger than l*(k) because l*(k) can be achieved with B' by never using m.

Claim l*(k) lies between 1 and 5 for k between 1 and 9.
Proof This follows as a corollary to the above three claims. l*(k) is strictly larger than 1 for k smaller than 9 because there is at least one number n for which there is no note in the basis, i.e. for which l(n) is strictly larger than 1. l*(k) is strictly smaller than 5 for k larger than 1 because there exists at least one number n other than 1 for which there is a note in the basis, i.e. for which l(n) = 1.

Let us come back to the main question. Is {1, 2, 5} optimally convenient? Let us check some other bases of cardinality 3. Perhaps powers of 2 are good? We have l({1, 2, 4}) = 17 / 9, the same as that of {1, 2, 5}! So we know there is no sacredness to the universally accepted denomination. Odd numbers might be better? l({1, 3, 5}) = 17 / 9, again. But no better. Consider the peculiar basis {1, 3, 4}. Here are the details:

The optimal payments are 1, 11, 3, 4, 14, 33, 34, 44, 144 and hence, l({1, 3, 4}) = 16 / 9, better than the others! From a few other bases I checked quickly, nothing seemed to do better. I believe {1, 3, 4} is optimal, and uniquely so. At least one conclusion is clear.

Claim {1, 3, 4} is more convenient than {1, 2, 5}.

So then, at least in terms of convenience of the users defined as is done here, {1, 2, 5} is not optimal. Is the choice of {1, 2, 5} then a misguided one, forced upon us by history than anything else? Or is there another way to look at this?

Coming back to the notion of convenience introduced here, is the choice of k = 3 a good choice? How would one otherwise choose k, and in turn, fix a basis for an optimal convenient consistent denomination?