“If a currency system could only have two coins, what should the values of those coins be?” – from Numberplay. Implicit in the question (the way it’s stated there) is that there are 100 cents in a dollar; I’m going to generalize to a dollar consisting of k cents.
Let’s say that we’re requiring that you be able to make change for any number of cents from 0 to k-1. and that we’d like to be able to do this with the smallest possible number of coins, on average. In order to make change for one cent we will need a one-cent coin. So there’s really only one parameter to play with — we’ll have two coins, of values 1 and n — and we want to choose n to minimize the average number of coins needed. We’ll assume that every possible amount of change from 0 to k-1 is equally likely. (This is probably not true, but the way in which it’s not true should evolve in tandem with the currency system. For example, in the US we have a 25-cent coin and so lots of prices are multiples of 25 cents. In the eurozone the comparable coin is a 20-cent coin; are prices which are multiples of 20 cents common?)
So we can break this down into, on average, how many 1-cent we’ll need and how many n-cent coins we’ll need when making change. On average we’ll need (n-1)/2 1-cent coins, if n happens to be a factor of 100. For example if n is 5 (that is, the other coin is a nickel) then on average we need 2 pennies, since we’re equally likely to need 0, 1, 2, 3, or 4 pennies. Let’s ignore the 1 and call this n/2. And to make change for m cents we’ll need m/n n-cent coins. On average we’re making change for k/2 cents, so on average we need k/2n n-cent coins.
So we want to minimize 
In the US case this means you want a penny and a dime. As it turns out an 11-cent coin would work just as well. The R function
f = function(k,n){sum(((0:(k-1))%%n) + floor((0:(k-1))/n))}
will give you the total number of coins needed to make each of 0, 1, …, k-1 cents out of 1-cent and n-cent coins. Interestingly, f(100, 10) and f(100, 11) both return 900 — that is, we’d need 900/100 = 9 coins, on average, if we had only pennies and dimes, or if we had pennies and 11-cent coins. For practical purposes, of course, we also want coins that are easily positioned for mental arithmetic.
It seems reasonable to guess that if you have three coins you’d want coins worth roughly 1, k1/3, and k2/3 cents, and in general denominations should be evenly spaced; this seems to be the principle that, say, euro coins/notes are based on. These are valued at 1 cent, 2 cents, 5 cents, and powers of ten times these. It’s also the principle that US currency would be based on except for the historical factors that have led to people not using half-dollar coins and $2 bills.) But it takes a bit more thought to figure out the optimal ways to make change in that situation, and it’s more than a one-liner to do the computation… any thoughts?
I’m looking for a job, in the SF Bay Area. See my linkedin profile.
Making change using as few coins as possible generally requires dynamic programming. The algorithm is pretty standard; see http://www.ccs.neu.edu/home/jaa/CSG713.04F/Information/Handouts/dyn_prog.pdf for one write-up.
What’s interesting about the US system is that a greedy algorithm starting with big coins will also give you the optimal solution. It wouldn’t be that hard to tweak–for instance, if we had a 12 cent piece, the greedy algorithm would give you five coins for 29 cents, but the optimal solution only needs three. I don’t know of any characterizations of the sets of denominations of coins for which the greedy algorithm works.
Here’s a question: Given that so many prices end in 99 cents, why isn’t there a 99 cent coin?
Cause of tax brah.
Reblogged this on lava kafle kathmandu nepal.
H. Lee’s comment raises an important point.
Suppose that Alice needs to pay Bob some amount of money. The system given here is optimal for situations in which Alice has to give exact change. But what about if Bob is allowed to give Alice change in return?
There are several ways you could measure optimality. We’ll use total coins exchanged as the measure. I’m also going to assume that there are no dollars. If you had a dollar note and a 1c coin, then you could spend 99c by giving $1 and getting 1c back.
Conjecture: If a “dollar” is n² cents, then the denominations of coin which give the lowest average number of coins over all transactions in the range 1c to n²-1c are (n-1) and n cents respectively.
It is true, by the way, for n²=100. The optimal denominations in that case are 9c and 10c. For example, it takes 14 coins to make 95c using 1c and 10c coins (9×10+5×1), but only 10 coins using 9c and 10c coins (5×10+5×9).
I haven’t thought about introducing whole dollars into the model yet.
By the way, you’ve proved that if a dollar is n² cents, then 1 and n cents are “optimal” denominations, but you haven’t proved uniqueness. I think you’ll find that 1 and (n+1) are also optimal if the size if a dollar is a perfect square.
Conjecture: For any sufficiently large value of k, there are exactly two optimal solutions:
1 and ⌊√k⌋
1 and ⌊√k⌋+1
Hello there! Do you know if they make any plugins to help
with Search Engine Optimization? I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good success.
If you know of any please share. Cheers!