Recently Michael left the following challenge in a comment:
I’ve been trying to optimize my change-carrying habits. What is the smallest amount of quarters, dimes, nickels and pennies one can carry while still being able to give perfect change (two decimals)?
It’s not 100% clear what Michael meant by “give perfect change”, but let’s assume the goal is to be able to make any amount between 1 and 99 cents. For non-US readers, US coins are worth 1, 5, 10, and 25 cents.
Some questions for exploration:
- What’s the smallest number of coins you can come up with that works? What are they?
- Are there multiple solutions, or is the solution unique?
- How can you prove that a proposed solution is optimal? Unique?
- Can you answer the question for a different system of coins? For example, I am currently spending the summer in Cambridge, England, where coins are worth 1, 2, 5, 10, 20, and 50 pence. What if you also include the 1- and 2-pound (100 and 200 pence) coins, and want to be able to make change for every amount up to 5 pounds (the smallest note)?
- The US and UK coin systems both have the property that a greedy strategy works for giving the smallest amount of change. That is, to make a certain amount of change with the smallest possible number of coins, you can just keep picking the biggest coin less than or equal to the remaining amount. What about coin systems without this property? Do they make this problem harder? Easier?
- If you got to design your own system of coins with whatever denominations you wanted, how would you design it so that the minimum number of coins needed to make all amounts between 1 and 99 cents is as small as possible? As LARGE as possible?
- What are some methodologies for attacking this sort of question in general?
Feel free to come up with your own generalizations as well. Post questions, discussion, and solutions in the comments but don’t peek until you’ve tried solving it! I’ve posted another change-making puzzle before as well; the discussion there might also give you ideas.