Problem of the Week 1009Making Change GreedilyA 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. © Copyright 2004 Stan Wagon. Reproduced with permission. |