Kind of an old link, but before I lose it again: slashdot thread on the problem of making change with as few coins as possible. Including pointers to Shallit's research on coin systems minimizing the expected number of coins, and some discussion of why, in general, greedy algorithms don't work for optimal change-making and instead dynamic programming may be required.




Comments:

None: another reference
2005-10-03T19:14:29Z

I believe one of Dennis Shasha's puzzle columns for Scientific American a few years back also posed the same problem. I am not sure if he knew of Shalit's work, or vice-versa.

None: Four coin \( \{1,a,b,c\} \) asymptotics, anyone?
2005-10-03T23:22:21Z

Quite awhile ago I sent a problem to the American Math Monthly asking for the asymptotic number of greedy-optimal \( \{1,a,b\} \) coin sets. I've tried to work out four coin asymptotics more than once without success, but have never been able to interest anyone else in the problem...so, here's another chance, everyone!

11011110: Re: Four coin {1,a,b,c} asymptotics, anyone?
2005-10-04T00:56:22Z

Presumably this long since appeared in the Monthly answers...

I calculated the probability that \( \{1,a,b\} \) (chosen randomly from pairs \( \le n \)) is greedy-optimal to be \( \frac{8}{3} n^{-1/2} \) (plus lower order terms), but the calculation was messy enough that I likely made a mistake somewhere.

It appears to be the case (e.g. applying Lemma 1 of Chang and Korsh, JACM 1976) that \( \{1,a,b\} \) is greedy-optimal iff \( a\le(b\bmod a)+\lfloor b/a\rfloor \). The messy part is calculating how many pairs \( a,b \) satisfy that inequality.

No idea how to extend this to \( \{1,a,b,c\} \).

None: Re: Four coin {1,a,b,c} asymptotics, anyone? 2005-10-04T06:31:28Z

Nope, no mistake, that's it, 8/3 etc, I'm pretty sure.