I'm a tutoring a student whose working on the classical coin changing problem. For those who are unfamiliar with problem or the greedy algorithm used for it. The goal is find the fewest number coins required to give $x$ change using quarters ($25¢$), dimes ($10¢$), nickels ($5¢$), and pennies ($1¢$). The greedy algorithm basically says pick the largest coin available. I know that the greedy approach is optimal as long as you have all the coins available for example: Find change for $16¢$.
Optimal solution: $1$ dime, $1$ nickel and $1$ penny $(10 + 5 + 1)$. Three total coins.
However, if you no longer have nickels available to choose. The greedy algorithm does not hold for every case. For example: find change for $40¢$. The greedy algorithm says to pick $1$ quarter, $1$ dime, and $5$ pennies $(25 + 10 + 1 + 1 + 1 + 1 + 1)$. Seven coins total. A more optimal solution is to pick $4$ dimes instead $(10 + 10 + 10 + 10)$. Four coins total.
He's suppose to prove that what is the most number of pennies an optimal solution can have and what is the most number of dimes that an optimal solution can have?
We both agree that without nickels available you must use pennies as long as $x < 9$ (assuming $x$ is change left). If $x \geq 10$ then it's better to pick a dime instead.
And in the case of dimes, the most dimes you can have is $4$ as long as $x < 50$. When $x \geq 50$ a more optimal solution is to use at least two quarters.
The problem I'm having is coming up with a solid proof for this. I can explain it in words but am unable to come up with a mathematical reasoning. I'm thinking proof by contradiction, but I don't know how to write one for this scenario. Any help would be appreciated.
Best Answer
If you want a general solution, check the papers "Canonical Coin Systems for Change-Making Problem", by Xuan Cai (arXiv:0809.0400v2), "Combinatorics of the Change-Making Problem", by A. Niewiarowska and M. Adamaszek (arXiv:0801.01.20v2), and "What This Country Needs is an 18c Piece", by Jeffrey Shallit.