Greedy Algorithm proofs.

Normally you show that that each move you make is better than the move any other algorithm you would make.

When I say the other algorithm doesn't agree with my "first move", I generally mean that the other algorithm doesn't make my first move at all, not as a first move, not as a second move, not as many move.

For example, making change.

1 quarter 2 dimes 2 pennies.


Let's say that there's another algorithm that purports to be better than yours.  So, does it differ in the number of quarters?  If so, can you "realign" the other guy's algorithm so that it matches you in quarters while not harming the other algorithm, by changing the other guy's quarters to match your number of quarters, can you guarantee that you've reduced the other guy's total number of coins or have at least remained the same?


PART OF THE ANSWER

Let's say the other guy matches me on quarters, but we differ on dimes.  If we differ on dimes, he can't have more dimes than I do, because I use as many dimes as possible, so if we disagree he must have at least one fewer dime than I do.  This means that he must have ten cents in nickels and pennies (because we agree on quarters and I have more dimes).  So he have 2 nickels, a nickel and 5 pennies or 10 pennies.  Either way, if he were to replace that coin combination with a dime, he would reduce the number of coins total, so he would improve his algorithm by agreeing with me on the number of dimes.