by Arjun Jain
What are the denominations of currency required to pay someone each and every amount of money, so that you need a minimum number of notes, i.e. you have the lightest wallet possible? So, suppose you want to pay someone M Rs., the best case is of course, if you have an M Rs. note, but that does not make much sense if you might have to pay other amounts as well.
To be precise, we want to find the minimum number of denominations, that will allow us to pay every amount below a certain number, say W. Further, we assume that both the payer and the receiver have the same denominations.
For every denomination, you have 3 options:
- 1. You either give some of those notes,
- 2. or you receive some of those notes from the receiver,
- 3. or you don’t do anything with those notes.
Now to make your wallet lighter, you would want to keep only one note of each denomination. So, we can replace ‘some’ by 1 in the above paragraph. More on this in the end.
Suppose the number of denominations required is N. Then let w=(,) be the N tuple having the N required denominations as elements. Also, let be the number of notes corresponding to . From the previous paragraph, we see that each can either be 1 (you give 1 note of denomination ), or -1 (you receive 1 note of denomination ) or 0 (you do not do a transaction of that denomination). So, let v=() be the N tuple having the s as elements.
Consequently, w.v=x, where and , for all n.
Recall that we have 3 options for each denomination- this suggests the use of Base 3 numbers or the Ternary number system. This is because in the ternary number system, we can represent any number with the use of only 0, 1, and 2 as digits compared to 0,1,2,3,4,5,6,7,8,9 in the decimal system. Eg.: 43=1121 in the ternary system as 43= ().
So, given a number , we have a unique ternary representation of y in the form w. where w=(1,3,9,27,…,) and =() with each being 0, 1 or 2.
To use this idea for our problem, all we have to do is to subtract (1,1,…n times) from to form ) with each being -1, 0 or 1.
Therefore, w.v=y-w.(1,1,…n times)=x.
Now our problem is solved. We can pay every amount equal to or below W Rs., where . Further, if we want to find the combination of notes required to pay a certain amount , we simply add to x and find the ternary representation of that number. Then we subtract 1 from each digit in this ternary representation and get our required combination. Note that as ternary representations are unique for any number (not allowing negative powers of 3 to appear in the representation), the combination to pay x is also unique.
As an example, suppose that N is 5, so W=121. Therefore we require only one each of the 1, 3, 9, 27, 81 Rs. notes. Now if we have to pay 83 Rs., 83+121=204=2.81+1.27+1.9+2.3+0.1=21120 in the ternary system. So, v=(1,0,0,1,-1), i.e. you give the 81 and 3 Rs. notes, and take back a 1 Re. note. Simple.
Extending this, if the person you had to pay did not have any money, this would not work. Then for the case where you are not allowed to accept any money from the other person, the binary system would work perfectly as you have 2 options then: to give a note of a particular(nth) denomination () or not do anything(). Here W has to be as we do not need to subtract (1,1,…n times) from as is equal to v.
So for W close to 121, say 127, N=7. Therefore, only one each of 1, 2, 4, 8, 16, 32, 64 Rs. notes is required. Then to give 83 Rs., as 83=1.64+0.32+1.16+0.8+0.4+1.2+1.1=1010011 (in binary system), you give the 64, 16, 2 and 1 Re. notes.
Now, you could be wondering whether keeping 2 or more notes of some other denominations, might be able to make your wallet lighter, but that is no true. So for example, in the base 5 number system, we have 0,1,2,3,4 as the basic digits which we would have to change to -2,-1,0,1,2 to make the case symmetric for both the payer and the receiver. In general if a is the base of the number system, n is the maximum number below which every amount can be paid, and N is the number of notes you would have to carry around, by a similar analysis as above, we get . Below is a graph with the x,y,z axes representing a, n and N respectively.
So, we can see that for a given y, z increases with x.
Does anyone know the logic behind choosing 1,2,5,10,20,50,100,1000 as the denominations that are actually used ?