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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.