I have the following problem:
We have coins of values $m_1,\ldots,m_k$, with $m_1 = 1$, with $m_i < m_{i+1}$ and such that $m_i$ divides $m_{i+1}$, for all $1<i<k$, then, given a quantity $X$, prove that a greedy algorithm that takes the biggest $j$ such such that $X-m_j$ is greater than or equal to 0, outputs $m_j$ and looks for the solution for $X-m_j$ would give the change for $X$ in the minimal amount of coins
I've tried to do it by induction over $X$, since I know the algorithm would give the optimal solution for $X-m_j$, then I just have to prove that that solution plus the coin $j$ would be optimal for $X$. By contradiction, if the optimal solution contains the solution for $X-m_j$ but not the coin $j$, then I can find enough coins of lesser value to make up for its value, but this cannot be since the solution wouldn't be optimal. But I'm struggling with the case that the optimal solution does not contain the solution for $X-m_j$, since there's little I can tell from it.
I can also see that if I have enough coins of certain value then I can change them for one coin of the next type, but I don't really know how to use it.
I'm aware that this can be seen as a duplicate, but all the other questions have very vague answers, claim this without proving it at all, or deal with very specific cases.
I'd like some help on finishing up this proof, many thanks.
Best Answer
Let's call a collection of coins minimal if it contains fewer than $\frac{m_{i+1}}{m_i}$ coins of value $m_i$, for any $i<k$. It's not obvious, without proof, that any such collection is the best way to represent its total value. However, any collection of coins that's not minimal is definitely not the best: we can just take $\frac{m_{i+1}}{m_i}$ of the coins of value $m_i$, and replace them with a single coin of value $m_{i+1}$.
Lemma. If a minimal collection of coins doesn't contain any coins of value at least $m_j$, then its total value is at most $m_j - 1$.
Proof. The largest possible value of such a collection is achieved when it contains the highest number of coins of value $m_i$ allowed, for each $i=1,\dots, j-1$. That highest number allowed is $\frac{m_{i+1}}{m_i} - 1$, in which case the total value is $$\left(\frac{m_2}{m_1} - 1\right) m_1 + \left(\frac{m_3}{m_2} - 1\right) m_2 + \dots + \left(\frac{m_j}{m_{j-1}} - 1\right) m_{j-1}.$$ Distributing, we get $$(m_2 - m_1) + (m_3 - m_2) + \dots + (m_j - m_{j-1})$$ which telescopes to $m_j - m_1 = m_j - 1$. $\square$
With this lemma, it's easy to show that the greedy algorithm works. Suppose we have an amount of money $X$, with $m_j \le X < m_{j+1}$. Whatever the optimal coin representation of $X$ is, it has to be minimal. By the lemma, since it has value $X \ge m_j$, it must contain a coin of value at least $m_j$. It can't have a coin more valuable than $m_j$, either, since $X < m_{j+1}$. So any optimal coin representation of $X$ must contain a coin of value $m_j$.
Therefore, to find an optimal representation, we can take out the coin of value $m_j$ that we know has to be there, and then somehow find an optimal representation of $X-m_j$. But this is exactly the greedy algorithm.