Making Change Greedily

by Stan Wagon. 
Problem 1009 for the  Macalester College Problem of the Week.

A system of coins is called "nice" if it can represent any amount of money and the greedy algorithm -- repeatedly take the largest coin that will fit -- for making change always uses the smallest number of coins possible. The American system of coins -- 1, 5, 10, 25, 50 -- is nice since, for any number of cents A, the greedy algorithm for breaking A into a combination of coins will use the minimal number of coins. For example, a greedy breakdown of $1.38 is 2 half-dollars, a quarter, a dime, and then 3 pennies, and $1.38 cannot be obtained in fewer than 7 coins. Any total can be made by using only pennies.

The old British coin system is another matter. It consisted of a halfpenny, a penny, threepence, sixpence, a shilling (12 pence), a florin (24 pence), a half-crown (30 pence), a crown (60 pence), and a pound (240 pence). We ignore here the guinea, worth 252 pence. And let us take the indivisible unit as the halfpenny. This system is not nice: a greedy approach to 48 pence would use three coins (half-crown + shilling + sixpence), while it can be done using just two florins.

Question: What is the largest coin in this system whose removal leads to a nice system?

Source: This problem is inspired by an amazing algorithm (unpublished, though it can be found on the web at http://citeseer.nj.nec.com/pearson94polynomialtime.html by David Pearson for determining in very fast time whether a set of coins is canonical (which is the technical term for "nice" above). I have implemented Pearson's algorithm in Mathematica and it is really a beautiful thing! Note: The related problem of determining the representation with the fewest number of coins is NP-hard.

GreedyChange[x_, coins_] := 
        Module[{y = x}, 
          Map[(q = Quotient[y, #]; y -= q #; q) &, coins]];

CanonicalQ[cc_] := 
        Module[{n = Length[cc], ans = True, coins = Reverse[Sort[cc]]}, 
          Do[gr = Take[GreedyChange[coins[[i - 1]] - 1, coins], 
                j]; 
msum = 
              1 + Total[gr]; 
w = 
              gr . Take[coins, j] + coins[[j]]; 
gr1 = 
              GreedyChange[w, coins]; 
If[
              msum < Total[gr1], 
              ans = StringForm["Minimal example is ``,greedy = ``,optimal = \
``, ``,``", w, gr1, 
                  PadRight[ReplacePart[gr, gr[[-1]] + 1, -1], n, 
                    0], Total[gr1], msum]], {i, 2, n}, {j, i, 
              n}]; 
ans];

US = {1, 5, 10, 25, 50};
CanonicalQ[US]

British = 
        2 {1/2, 1, 3, 6, 12, 24, 30, 60, 240};
CanonicalQ[British]

Select[
      Table[{British[[i]]/2, 
          CanonicalQ[British[[DeleteCases[Range[9], i]]]]}, {i, 
          9}], #[[2]] &]

There are at least two coins that make the British system (or subset we mentioned) nice, the 24-pence florin and the 30-pence half-crown. Since the problem asked for the larger, we get the half-crown.

Comments.

1. This problem is inspired by an amazing algorithm (unpublished, though it can be found on the web at
<<http://citeseer.nj.nec.com/pearson94polynomialtime.html>> by David Pearson for determining in very fast time whether a set of coins is canonical (which is the technical term for "nice" above). I have implemented Pearson's algorithm in Mathematica and it is really a beautiful thing! Code will be sent out next week. Note: The related problem of determining the representation with the fewest number of coins is NP-hard.

The Pearson algorithm:

Let C be a set of n coins {c(i)}, where we assume c(1) > c(2) > ... > c(n), and c(n) = 1.
C is called "canonical" if the greedy algorithm for making change always yields the minimal number of coins.
Example: {50, 25, 10, 5, 1} is canonical
               {64, 50, 25, 10, 5, 1} is not (75 = 50 + 25 = 64 + 10 + 1 is the smallest bad example)

Pearson's (amazing) O(n3) algorithm for determining whether C is canonical.

For each i and j such that 2 ? i ? n and i ? j ? n, do:
     1. Compute the greedy representation of c(i - 1) - 1
     2. Take the leftmost j entries of the result of (1) and add 1 to the jth entry; then pad on the right with 0s to get an n-vector M.
     3. Let w be the number represented by M (its dot product with C). Check whether the number of coins in the greedy rep'n of w is greater than the number of coins in M. If it is, stop and compare w to the smallest such w found in previous iterations. If it is smaller, update the previous best to the current w.
     4. If no such w is found, then C is canonical. If some w's have been found, then the smallest among them is the minimal example showing that w is not canonical.


2. A problem I have not thought about: Suppose S a set of coins is not nice. Suppose it becomes nice after removal of coin n. And it also becomes nice upon removal of coin m. Is it necessarily nice if both m and n are removed?

Solution by John Guilford (Agilent) and Stan Wagon.

First double the values of all the coins to get integers: 480 120 60 48 24 13 6 2 1. Now we can simplify things by noting that if each coin (except for the "1") is a multiple of the next smallest coin, N, then we can make an equivalent problem by deleting "1" and dividing the rest by N (for the US system this is equivalent to ignoring pennies and working in multiples of nickels, which is how we usually make change). Doing this repeatedly with 3, 2, and 2, reduces the set as follows:

480 120 60 48 24 13 6 2 1 -> 240 60 30 24 12 6 3 1 -> 80 20 10 8 4 2 1 -> 40 10 5 4 2 1

So the bad example, 48, becomes 8=5+2+1, when 8=4+4 is optimal. So it is natural to consider removing 5 from the list (since we want the largest) to see if it then becomes nice. It turns out that either works. Let's try 5. This leaves the set 40, 10, 4, 2, 1. The reduction trick given above reduces this to 20, 5, 2, 1. We need to prove that this is nice. Let us first show that the greedy repn. of any number from 0 to 19 is optimal. This can be done by checking each one. Example: 13=5+5+2+1 by greedy. But it cannot be done in 3 since the only values obtainable with 3 coins are 3, 4, 5, 6, 7, 8, 9, 11, 12, and 15. Similar work shows that all values from 0 to 19 are nice. Actually, we will need to know that all values up to 34 are nice, and this can be checked by hand.

Now use induction on the number of 20s in the greedy repn. of n. Suppose n = (a,b,c,d) where a is the number of 20s. If a = 0, this is the base case of the induction, handled by the 0-19 case above.
Let m = n - 20. Then (a-1, b, c, d) is the greedy repn. of m, and so it must be the optimal rep. by an inductive assumption. The number of coins is K=a+b+c+d-1. We need to show that n cannot be represented with this many coins. Suppose it were possible and consider the optimal repn. There would have to be at least one 20 coin, for if not the repn has the form (0, r, s, t). Then r<4 (else a 20 could be substituted) and s <10 and t<2. So the total is at most 15+18+1=34, and we checked that the conclusion is good for such totals.

So we know there is at least one 20 coin. Removing it would yield a repn. of m with K-1 coins, contradicting optimality of K.

Removing a 5 in the reduced system corresponds to removing a 5 x 2 x 2 x 3 = 60 in the original (doubled) system, and this is the same as getting rid of the 30-pence coin, the half-crown. QED.

The Mathematica code above implements the greedy algorithm and then Pearson's algorithm. The last bit shows that there are two coins that could have been removed, the half-crown or the florin.