# Proving a greedy algorithm

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?

Questions

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:

Greedy-Pay(x)
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.)

• 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? – rus9384 Sep 26 '17 at 21:52
• @rus9384 there are unlimited coins / bills so it always works out. – Anters Bear Sep 26 '17 at 22:47