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 always 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) its an optimal algorithm, in the sense that it minimizes the total number of coins given out. But we know that there are some cases (classic British coins, as in the in-class exercise #2) for which it doesnt 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 optimal change (again, assuming the existence of a 1-cent piece).

Either show that this is true by outlining a proof that the greedy choice and optimal substructure properties hold, or prove that it isnt true in general by giving a single counterexample.