On Thursday, June 5, 2003, at 10:38 AM, Thane Plambeck wrote:
Three integer coin values 1 < a < b will make optimal (smallest number of coins) change for all amounts using the greedy ("pick the largest possible coin first") algorithm if and only if there is an integer m so that Floor[b/m] = a. [...] Is there a similar criterion for four coins 1 < a < b < c?
I have no idea, but I'll mention (in case you didn't already know) that there is a polynomial-time algorithm that determines whether an arbitrary system of denominations has the property that the greedy algorithm is always optional. See Jeff Shallit's article "What This Country Needs is an 18-cent Piece" in the most recent Mathematical Intelligencer, available from his web page, http://www.math.uwaterloo.ca/~shallit/papers.html Actually, looking at the algorithm, the answer to your question is probably "yes", though it won't be quite as simple as for 3 coins, but I don't have the time to think this through right now. --Michael Kleber kleber@brandeis.edu