Getting Perfect Change

If you are buying an item for $1.08 and you give $5 to the cashier then you are going to get a lot of coins in your change. However, if you have $5.08 then giving the entire amount to the cashier not only rids you of the $0.08 that you were carrying, but it also cuts out all the quarters, dimes, nickels, and pennies in the change the cashier gives to you.

It does not have to be an exact match in the coins department. If you are buying an item that costs $4.80 and you have a five dollar bill and a nickel in your purse then you end up with different sets of coins depending on whether you give $5 or $5.05 to the cashier. If you give just the $5 then you end up with the nickel that you started with plus two dimes. If you pay with $5.05 then you end up with one quarter, effectively and efficiently converting what would have been two dimes and a nickel into the larger-denomination quarter.

So, how do you figure out what is the best amount to give to the cashier? How much "extra" change should you give to the cashier so that the net result is higher denominations in your purse?

Answer: An easy way to think about solving this problem is too not focus on what you give to the cashier. Instead you focus on what you do not give to the cashier! For example, if you have a five dollar bill, one quarter, and three pennies ($5.28) in your purse and you are buying an item that costs $4.93 then focus on the fact that you will have $0.35 after the transaction is done. You hope that that $0.35 will be in the largest denominations possible, one quarter and one dime. Since you already have a quarter in your purse, hold on to it. If you also had a dime then you would hold on to that too. You give the rest to the cashier. You are giving $5.03 in this case. Your change is $0.10, which is the dime that you were hoping for.

If the cashier always gives your change to you using the highest denominations possible then this always works!:

Figure out what bills and coins you hope to have in your purse after the transaction is over.
Retain only those bills and coins that take you toward this goal. Give the rest to the cashier.

Proof:

Define "perfect coinage" to mean that an amount is had in the highest denomination bills and coins possible.
Observe that any subset of perfect coinage is also perfect coinage. That is, if no number of smaller denomination bills and coins could be traded up for one or more larger ones then, throwing away some of the bills and coins is not going to suddenly enable you to trade up for larger ones.
Observe that the bills and coins that you hope to have when the transaction is over is perfect coinage and that the bills and coins that you hope to receive from the cashier are a subset of that, and thus are perfect coinage for the amount they represent.
Observe that that for any given total, there is a unique way to have it as perfect coinage. (You could contruct the perfect coinage by starting with an empty purse and repeatedly choosing to add to your purse the largest denomination bill or coin that does not take you over the target amount.)
Putting it all together: Because we have assumed that the cashier always gives your change to you using the highest denominations possible – that is, as perfect coinage – and because we know there is only one way to give perfect coinage for that amount, it must be the case that the perfect coinage that you are hoping to receive is one and the same as the perfect coinage that the cashier will give to you.

Note that if you start with perfect coinage then a slight variation of this approach works with those cashier machines that give your change to you the moment that you have given at least the total amount due. If you make sure that the largest denomination of the bills and coins that you are giving to the cashier machine is given last then you will end up with perfect coinage.