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?
 A: 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".
Good luck with your investigations.
A: 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.
