The item I had just bought cost 29 cents. I gave the cashier a dollar bill, and she gave me two quarters, two dimes, and a penny in change. She could just as well have given me seven dimes and a penny or some other combination of coins adding up to 71 cents, but there's no way she could have made change with fewer than five coins.

Most businesses in the United States make change using just four different types of coins: 1 cent (penny), 5 cents (nickel), 10 cents (dime), and 25 cents (quarter). This distribution of coinage suggests an interesting question: Is it the most efficient way to make change? In other words, is this the optimal choice of coin values for minimizing the number of coins required to handle typical transactions?

Computer scientist Jeffrey Shallit of the University of Waterloo has worked out an answer. In the current issue of the Mathematical Intelligencer, he contends that "what the U.S. needs is an 18-cent piece."

In finding coin denominations that minimize the average cost of making change, Shallit assumed that every amount of change between 0 and 99 cents is equally likely. For the current four-denomination system, he found that, on average, a change-maker must return 4.70 coins with every transaction.

He discovered two sets of four denominations that minimize the transaction cost. The combination of 1 cent, 5 cents, 18 cents, and 25 cents requires only 3.89 coins in change per transaction, as does the combination of 1 cent, 5 cents, 18 cents, and 29 cents.

"We would therefore gain about 17 percent efficiency in change-making by switching to either of these four-coin systems," Shallit says. "The first system possesses the notable advantage that we only need make one small alteration in the current system. We could speed up customer service just by replacing the dime with an 18-cent piece."

"The trouble with 18-cent pieces," he admits, "is that it's hard to figure out the best way to make change in your head."

Instead of replacing the popular dime with another coin, it's also possible to see whether the addition of a fifth coin would help. It turns out that the greatest improvement in change-making efficiency would occur with the addition of a 32-cent coin. This reduces the average cost to 3.46 coins per transaction.

Interestingly, if the unpopular 50-cent coin were used more frequently, the maximum improvement would come from introducing an 18-cent coin. That's "yet another reason to add an 18-cent piece to U.S. coinage," Shallit declares.

The same issue of efficiency can be addressed for coin denominations in other countries. Canada, for example, has coins with values 1 cent, 5 cents, 10 cents, 25 cents, 100 cents, and 200 cents. Assuming that each amount of change between 0 and 499 cents is equally likely, Shallit's calculations show that the average cost of making change would fall from 5.90 to 4.58 coins per transaction with the addition of an 83-cent coin.

Similarly, the new Euro system introduced by the European Union would benefit from the addition of a 1.33- or 1.37-Euro coin.

Despite its apparent inefficiency, the current U.S. system of coin denominations has a striking advantage over many other possible systems. When most people make change, they give the coins with the largest possible value first, then the next largest, and so on. Computer scientists call such a scheme the "greedy algorithm."

"The nice thing about the current system is that the greedy algorithm always gives the smallest number of coins possible within the system," Shallit says. "So it's easy to make change."

For other sets of denominations, the greedy algorithm doesn't always give the minimum number of coins. For example, if coins had the values 1, 7, and 10, the greedy algorithm would represent 14 as 10 1 1 1 1, whereas the combination 7 7 uses fewer coins.

The United States has experimented briefly with extra coin denominations. At one time or another in the distant past, the U.S. mint issued half-cent, two-cent, three-cent, and 20-cent pieces?but it never produced an 18-cent coin.

Comments are welcome. Please send messages to Ivars Peterson at ip@sciencenews.org.

Fragments of Infinity Ivars Peterson is the mathematics writer and online editor at Science News. He is the author of The Mathematical Tourist, Islands of Truth, Newton's Clock, Fatal Defect, The Jungles of Randomness, and Fragments of Infinity. He also writes for the children's magazine Muse (see MatheMUSEments at http://home.att.net/~mathtrek/). The Mathematical Association of America has published a collection of his online MathTrek articles.

Coins for Making Change Efficiently