Hey so I'm studying for a midterm and I've run into this problem in the material. I'm not sure how to go about solving it. If I use regular induction in part a, I get something a bit tautological. Any suggestions?


As we all know, US dollar is the official currency in United States. There are different bills of value 100, 50, 20, 10, 5, 2, 1 , and coins of value 1, 0.50, 0.25, 0.1, 0.05, 0.01. In this problem we consider the problem of buying something with the smallest number of bills/coins. A simple way to pay x dollars is to use the following Greedy-Pay algorithm:

   While x > 0
      Let u be the largest value bill/coin such that u <= x
      Pay the bill/coin with value u
      Let x = x - u

Prove that if you have unlimited number of bills of {1, 2, 5, 10} dollars (and you don’t have any other bills/coins), no matter what x is (as long as it is a multiple of 1) the Greedy-Pay algorithm minimizes the number of bills/coins used for the payment. (Change is not allowed here. For example, you cannot pay 9 by a 10 bill and get 1 back.)

  • $\begingroup$ And what if price is 9.5 while you can use at least 1 dollar bill? If you can't change, there is no solution at all. Or do we ignore those 50 cents? $\endgroup$ – rus9384 Sep 26 '17 at 21:52
  • $\begingroup$ @rus9384 there are unlimited coins / bills so it always works out. $\endgroup$ – Anters Bear Sep 26 '17 at 22:47

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.