$2.[4$ pts$]$: Consider the standard greedy algorithm for making change. Namely, give the user change by giving them as many as possible of the highest denomination coin or bill, then as many as possible of the next highest coin or bill, etc. We know that this will al ways give correct change $($assuming that there is a $1-$"cent" coin defined$).$ We also know that for some sets of coins $($such as American coins$)$ it's an optimal algorithm, in the sense that it minimizes the total number of coins given out. But we know that there are some cases $($such as classic British coins$)$ for which it doesn't work.

It has been hypothesized by some students that if every coin is at least twice as valuable as the next smaller coin, this greedy algorithm always provides minimal number of coins for a given amount of change $($again$,$ assuming the existence of a $1-$"cent" piece$).$

Either show that this is true by outlining a proof that the greedy choice property holds, or prove that it isn't true in general by giving a single counterexample. $\backslash (\{\}^\{2\}\backslash )$

Solution: