The change-making problem is the problem of representing a given value
with the fewest coins possible. We investigate the problem of determi
ning whether the greedy algorithm produces an optimal representation o
f all amounts for a given set of coin denominations 1 = c1<c2<...<c(m)
. Chang and Gill (1970) show that if the greedy algorithm is not alway
s optimal, then there exists a counter-example x in the range c3 less-
than-or-equal-to x<c(m)(c(m)c(m-1)+c(m)-3c(m-1))/c(m)-c(m-1). To test
for the existence of such a counterexample, Chang and Gill propose com
puting and comparing the greedy and optimal representations of all x i
n this range. In this paper we show that if a counterexample exists, t
hen the smallest one lies in the range c3+1<x<c(m)+c(m-1), and these b
ounds are tight. Moreover, we give a simple test for the existence of
a counterexample that does not require the calculation of optimal repr
esentations. In addition, we give a complete characterization of three
-coin systems and an efficient algorithm for all systems with a fixed
number of coins. Finally, we show that a related problem is co-NP-comp
lete.