Optimizing the number of coins

Cash management is a real pain for retailers. It costs a lot to count and transfer coins and notes to Banks. It also hides cost with the time lost at the cashier when customers need to look for the tiny coins in the wallet trying to get the exact change. Most of the times, it ends by giving slightly more so that the cashier need to look for the small (but heavy in the pockets) coins. All this is time consuming and decreases productivity (a vital criteria for retailers profitability). 

How could we improve this process ?

Jeffrey Shallit  a professor in Waterloo, University of Canada is a specialist of "combinatorics on words, algorithmic number theory, etc...". He wrote a very interesting note about how to optimize the change of coins or in other words, what is the most efficient combination of coins to minimize the handling. 

In the US monetary system you may find just 4 kind of coins : 1 (penny), 5 (nickel), 10 (dime) and 25 (quarter). The average number of coins necessary to make change on 1 USD is 4,7 per transaction (assuming that every amount of change is evenly distributed between 0 and 99). You can maximize this result with a 4 coins combination: 1, 5, 18, 25 to get an average of 3,89. Obama's change for improving efficiency would be to switch the Dime to a 18¢ coin. This proposal would also have the advantage of favourizing mental calculus in the population...

PS: In Euro countries, we have 6 available coins (1ct, 2ct, 5ct, 10ct, 20ct, 50ct, 1€, 2€). This set, for a 5€ change, gets a poor average of 4,6. 

Let's switch our coins for a more efficient combination to reduce costs and waiting lines !