The most common coins in U.S. circulation are worth 1¢, 5¢, 10¢, and 25¢. University of Waterloo computer scientist Jeffrey Shallit found that with this system the average cost of making change is 4.7; that is, if every amount of change between 0¢ and 99¢ is equally likely to be needed, then on average a change-maker must return 4.7 coins with each transaction.

Can we do better? Shallit found two four-coin sets that reduce the average cost to a minimum: (1¢, 5¢, 18¢, 25¢) and (1¢, 5¢, 18¢, 29¢). Either reduces the average cost to 3.89.

“We would therefore gain about 17% efficiency in change-making by switching to either of these four-coin systems,” he writes. And “the first system, (1, 5, 18, 25), possesses the notable advantage that we only need make one small alteration in the current system: replace the current 10¢ coin with a new 18¢ coin.”

(Jeffrey Shallit, “What This Country Needs Is an 18¢ Piece,” Mathematical Intelligencer 25:2 [June 2003], 20-23.)