# Questions on the proof of make change problem using greedy algorithm

I recently learned the proof of the greedy algorithm solution to make change problem:

There's a set of coins $\{c_1 < c_2<...<c_{i-1}<c_i\}$. $c_i$ is an integer and $c_{i+1}=q\cdot c_i$ where $q$ is an integer. Given number $x$ what is the least amount of coins needed to pay $x$ of some currency?

The solution will use a greedy algorithm. In order to prove that greedy algorithm is correct we suppose that we have: $$\{c_1, c_2,...,c_{i-1},c_i\} \quad\text{coins set}\\ k_1, k_2,...,k_{i-1},k_i\quad\text{how many times}\quad c_i \quad\text{is repeated}\\ c_1=1$$ We also suppose that there's another different algorithm that works and in it there're $p_i$ repetitions of $c_i$.

Then $p_i<k_i$. Then we have some "deficit" on $p_i$ part then the deficit must be resolved by some former combination of $p$ and $c$.

We'll prove that the deficit will never be resolved because:

$$p_1\cdot c_1<c_2\qquad (1)$$ then: $$p_1\cdot c_1 \le c_2-c_1 \implies\qquad (2)\\ p_2\cdot c_2 \le c_3-c_2 \implies\\ \vdots\\ p_i\cdot c_i \le c_i-c_{i-1} \implies$$ Now if we sum up the LHS and RHS we get: $$\sum_{k=1}^{i-1}p_k\cdot c_k\le c_i-c_1<c_i$$ which proves that the deficit is never made up for by $\sum p_k\cdot c_k$.

Two things I can't grasp:

why does $(1)$ and $(2)$ hold?

• But the greedy algorithm doesn't solve the problem! For example, suppose the coins are $\{1,15,25\}$. Then to make change for $30$, it is best to use $(15,15)$, but the greedy algorithm uses $(25,1,1,1,1,1)$. – Théophile Oct 19 '17 at 14:31
• @Théophile this particular algorithm that I described is not always correct I meant some greedy algorithm in general. I'll delete the description of my algorithm. – Yos Oct 19 '17 at 14:32
• Hmm. What do you mean by "some greedy algorithm in general"? Which greedy algorithm solves this problem? – Théophile Oct 19 '17 at 14:53
• @Théophile Note the extra condition that $c_{i+1}= qc_{i}$ for integer $q$, which is why your counterexample does not work for this variant. – Michael Biro Oct 19 '17 at 14:55
• @MichaelBiro Ah, I see. That condition was added in a later edit. – Théophile Oct 19 '17 at 15:13

(1) is true because you could have used $c_2$'s instead if $p_1c_1 \geq c_2$.

(2) is true from (1) because $qc_1 = c_2$ for some integer $q$, so if $p_1c_1 < c_2$ then $(p_1 + 1)c_1 \leq c_2$

• Can I say that because $p_1c_1<c_2$ then $(p_1+1)c_1\le c_2$ because we're dealing with integers and the minimal step is $1$? – Yos Oct 19 '17 at 15:16
• @Yos Since $c_1 = 1$ here, yes. However, the other steps require the same conclusion that $(p_i+1)c_i \leq c_{i+1}$ for all other $c_i$, which won't necessarily be $1$. You want to use the fact that $c_{i+1}$ cannot lie between $p_ic_i$ and $(p_i + 1)c_i$ – Michael Biro Oct 19 '17 at 15:18
• So is it because we proved this on $(p_1+1)c_1\le c_2$ that we can also use the proof on $(p_i+1)c_i\le c_{i+1}$? – Yos Oct 19 '17 at 15:20
• @Yos The argument is the same. Since $c_{i+1}$ is a multiple of $c_i$, it cannot lie strictly between two consecutive multiples of $c_i$. – Michael Biro Oct 19 '17 at 15:22