The coin change problem is as follows. Given coins with values $1 = c_1 < c_2 < \cdots < c_k$ and an amount $M$, find nonnegative integers $a_i$ such that $\sum a_i c_i = M$ with $\sum a_i$ as small as possible. (The $1$ is so that a solution is possible for any $M$.)
The greedy algorithm, taking as many $c_k$ as possible, then as many $c_{k-1}$, and so on, is not always optimal for this problem (e.g. coins 1, 3, 4, target amount 6).
For $M$ large, there are always optimal solutions to the coin change problem using the largest coin $c_k$. Explicitly, Chan and He in More on Change Making and Related Problems show that if $M > c_{k-1}c_k$ then there are optimal solutions using $c_k$. The proof is as follows: if $\sum_{i=1}^{k-1} b_i c_i = bc_k$ then no optimal solution has $a_i \geq b_i$ for all $i$, since we can replace $\sum_{i=1}^{k-1}b_i c_i$ with $bc_k$ to get a strictly better solution. Now suppose we have any solution using $N$ non-$c_k$ coins with values $x_1, \ldots, x_N$, and let $s_i$ be the $i$th partial sum of the $x_i$ for $i \geq 0$. If $N \geq c_k$ then two of these partial sums must be congruent mod $c_k$, so there is a sum of $x_i$s divisible by $c_k$, so the solution can be improved. Thus any optimal solution not using $c_k$ must be to a problem with $M$ at most $c_{k-1}c_k$.
Is there a smaller bound $m$ such that if $M\geqslant m$, there are always optimal solutions that use the largest coin? If the greedy algorithm works for a particular set of coins then $m=c_k$ works, but I am interested in bounds valid for any coins.