# How do I prove a combinatorial statement about the change-making problem when using the greedy algorithm?

Let $D$ be set of denominations and $m$ the largest element of $D$. We say that $c$ is a counterexample if the greedy algorithm gives an answer different from the optimal one.

Now, apparently, if for a given set $D$, the greedy algorithm does not return an optimal solution, then the smallest $c$ will be smaller than $2m-1$.

Is this really true? How can we prove it? If not, is there a relatively small range to look for the smallest counterexample?

• I think you need some assumptions, e.g. for coins $\{2-\sqrt{2}, 1, \sqrt{2}\}$, the first natural number for which the greedy algorithm doesn't work is $3 > 2\sqrt{2}$. If you are talking about coins $\in \mathbb{N}$, then I remember something similar, but I can't recollect the source. The articles mentioned by Hendrik look promising, however ,it was not there where I saw it. – dtldarek Dec 1 '12 at 11:12

The paper "Optimal Bounds for the Change-Making Problem" (by Kozen and Zaks, TCS 1994) gives a bound of $x < c_M + c_{m-1}$ where $x$ is the counter example and $c_m$ and $c_{m-1}$ are the largest and second largest coin. They claim the bound is optimal. (I just browsed the paper, and I did not take the time to understand whether this automatically means you cannout expres it in the largest coin value)

Jeffrey Shallit (famous for his paper "What this country needs is an 18c piece") in 1998 posted a bibliography on the subject: mathforum. Shallit adds "... it is a problem in which it is notoriously easy to make wrong conclusions -- some of them have even been published".

I recently came up with 1 solution that seemed to show if the given 2 conditions are satisfied, the greedy algorithm would yield the optimal solution.

a) The G.C.D (All the denominations except 1) = 2nd Smallest denomination.

b) The sum of any 2 consecutive denominations must be lesser than the 3rd consecutive denomination.

For eg. $c_2 + c_3 < c_4$.

(Where $c_1 = 1; c_2, c_3, c_4$ are coin denominations in ascending order).

I understand this is not a complete solution. However, I believe that if these 2 conditions are met, the greedy algorithm will yield the optimal solution.

• Duplicate answer. As there, this would be more useful if accompanied by a proof. – robjohn Mar 6 '13 at 9:56
• This answer seems to be incorrect, as I explained in the other place that it was posted. – Joseph Sible-Reinstate Monica Mar 29 '18 at 17:39