Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
When solving the problem of coin exchange by greedy algorithm, why will we will always have the correct result if the coin values are $1, a, a^2, \cdots, a^n$, where $a\ge 2$ and $n\gt 0$?
For example, if $a = 3$, $n =3$, we get the following coin values: 1, 3, 9, 27. When total exchange is 16, answer is 4 coins, as returned by greedy algorithm, $16=9+3+3+1$.
For the coin values: 1, 3, 9, 27, suppose $16 = a_0 + 3a_1 + 9a_2 + 27a_3$ is the coin exchange with minimal number of coins. Note that $16\equiv a_0 \equiv 1(\operatorname{mod}3)$. If $a_0 \ge 3$, then we can subtract 3 from $a_0$ and add 1 to $a_1$ to obtain coin exchange with less number of coins. So, $a_0$ must be the remainder of 16 divided by 3. Hopefully, you can see where I am going.
All numbers or variables below are nonnegative integers. $(d_nd_{n-1}\cdots d_0)_a$ means the integer with those digits in base $a$, i.e., $(d_nd_{n-1}\cdots d_0)_a=\sum_{i=0}^{n}d_ia^i$ where $d_i\lt a $ for $i\le n$.
Here is the general theorem.
(Greedy algorithm works for power coins) Let $a\ge2$ and $n\ge0$. If $e_na^n+(e_{n-1}e_{n-2}\cdots e_0)_a=\sum_{i=0}^nc_ia^i$, then $ \sum_{i=0}^ne_i\le\sum_{i=0}^nc_i$.
Proof by mathematical induction on $n\ge0$.
The base case, when $n=0$ is trivial.
Suppose it is true for some $n\ge0$. Let us check the case of $n+1$. Suppose $m=e_{n+1}a^{n+1}+(e_ne_{n-1}\cdots e_0)_a=\sum_{i=0}^{n+1}c_ia^i$. Note that $e_0$ is the remainder of $m$ divided by $a$.
If $c_{0}\ge a$, we can subtract $a$ from $c_0$ and add $1$ to $c_1$ to reduce sum $\sum_{i=0}^{n+1}c_i$. Without loss of generality we can assume $c_{0}\lt a$, i.e., $c_0$ is also the remainder of $m$ divided by $a$.
Now let $m'=(m-e_0)/a=(m-c_0)/a$. Then $m'=e_{n+1}a^{n}+(e_{n}e_{n-1}\cdots e_1)_a=\sum_{i=0}^{n}c_{i+1}a^i$. By induction hypothesis, we know $\sum_{i=0}^ne_{i+1}\le\sum_{i=0}^nc_{i+1}$. Adding $e_0=c_0$ to both sides, we obtained the wanted inequality for the case of $n+1$. Q.E.D.
What is left to be explained is that $\sum_{i=0}^ne_i$ does come from the greedy algorithm. That easy task will be left for interested readers to verify.
