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$.

  • $\begingroup$ Welcome to Computer Science! I am very interested in how you know "we will always have the correct result" in these cases. Could you please provide a url or reference in the question? $\endgroup$ – Apass.Jack Nov 3 '18 at 5:55
  • $\begingroup$ You can use LaTeX to typeset mathematics. I edited to show you how; we also have a brief tutorial. $\endgroup$ – Apass.Jack Nov 3 '18 at 10:58
  • 1
    $\begingroup$ I just updated the question on behalf of the asker. It should be clear now. $\endgroup$ – Apass.Jack Nov 3 '18 at 17:36
  • $\begingroup$ Thanks, @Apass.Jack -- that's much clearer. $\endgroup$ – David Richerby Nov 3 '18 at 18:46
  • $\begingroup$ @Apass.Jack, thanks for the corrections! The fact is that there is no basis for my words. I said this without any arguments, I just checked some numbers, it was so. $\endgroup$ – BoberMod Nov 3 '18 at 22:49

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.

  • $\begingroup$ This should always work if any but the smallest coin have a value that is a multiple of the previous coin. $\endgroup$ – gnasher729 Nov 3 '18 at 16:02
  • $\begingroup$ @gnasher729 Sharp observation! The proof also works after slight modification. $\endgroup$ – Apass.Jack Nov 3 '18 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.