Coin Changing



Suppose you need to make change for 67 cents. You want to make up that sum using the fewest number of coins possible. Pennies, nickels, dimes, quarters, and half dollars are available.


You choose one half dollar, one dime, a nickel, and two pennies. That does it:

50 + 10 + 5 + 1 + 1 = 67 cents.
Five coins in total were required.



In general, one way to make change is to use the greedy algorithm: to make up a given sum, repeatedly choose the largest coin less than or equal to the sum remaining, until the desired sum is obtained.

This is exactly how millions of people make change, every day.



In fact, the greedy algorithm always gives the minimum number of coins, for every possible amount.

However, the optimality of the greedy algorithm is in fact merely a property of the particular coin values (1, 5, 10, 25, 50) we use in the United States.

Perhaps for some other choices of coin values—in some bizarre, unfamiliar country maybe—could the greedy algorithm be non optimal?

The answer is yes. For example, suppose the coin values are 1, 3, and 4. Then to make change for 6 cents, the greedy algorithm arrives at

4 + 1 + 1 = 6 cents,
for a total of three coins, but a better choice would be the "non-greedy" choice

3 + 3 = 6 cents,
which requires only two coins.

Here be boojums

Now fix an integer N > 3, and choose two coin values a and b, 1 < a < b < N uniformly at random amongst all such choices of integer values a and b.

What is the probability that the greedy algorithm always makes optimal change using the coin set (1,a,b)?

I posed this problem in the American Mathematical Monthly [Volume 96, Number 4 (April 1989), pg 357].

The answer is asymptotically

8/3 N**(-1/2) + O(1/n)

if memory serves.

Vorpal blade

Anyone care to provide asymptotics for four coins?