Making Change

Roland Piquepaille writes "There are mostly four kinds of coins in circulation in the U.S: 1 cent, 5 cents, 10 cents, and 25 cents. But is it the most efficient way to give back change? This Science News article says that a computer scientist has found an answer. "For the current four-denomination system, [Jeffrey Shallit of the University of Waterloo] 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." He also found that change could be done more efficiently in Canada with the introduction of an 83-cent coin and in Europe with the addition of a 1.33- or 1.37-Euro coin. Check this column for more details and references." The paper (postscript) is online.

Or, even better ...

[simong_oz]

Do what Australia did a while back and round everything to the nearest 5c and get rid of 1c and 2c coins entirely (so now Australian coins are 5c, 10c, 20c, 50c, $1 and $2). I couldn't decide whether I liked it to start with, but after a little while you realise just how much shrapnel you carry around and have no intention of using except to empty it from your pocket/wallet at the end of every day. Every time I go to another country and have to again deal with 1/2 cent/euro cent/pence/etc I just appreciate this move even more.

Re:Instead...

[jmv]

In France (and probably other countries) most of the prices end in .00 and the taxes are already included (unlike Canada where I live). It's much simpler that way. If only there was a way to convince stores to do that in here...

Re:Instead...

[pi radians]

If only there was a way to convince stores to do that in here...

Its not up to the store, but the law. You must show the PST and GST on every sale in Canada. There was some debate a couple years ago about changing it to hidden costs, but that seems to have been quelled with recent wars and weed laws.

Re:I hate math...

[Alsee]

The logic for determining change is really easy for a cashier. start with the largest coin and work your way down until it all adds up.

I can't think of an example where that doesn't work in a 1,5,10,25 system, but it is definitely not a valid rule in general. For example in a 1,40,41 system you can give 80 cents change with two coins, but your method would use fourty coins.

-

18-cent is really a red herring - 2-cent works too

[bryane]

Turns out that featuring 18-cent is more for sensationalism than reality. The article says adding a 2-cent coin will accomplish the same goal of reducing the average number of coins below 4. It would also keep change-making easy.

The article also assumes a uniform distribution of change between 1 and 99 - not likely, given how things work.

Just get rid of the pennies

[YrWrstNtmr]

The US military overseas has done away with pennies (except at the post office)

The ticket price still reflects .99 or whatever, but the price at the register is rounded down or up as needed.
.08, .09, .00, .01, .02 = .00
.03, .04, .05, .06, .07 = .05

It averages out over time, especially when you buy more than one item.

Re:Forget it.

[omega_cubed]

Quoth Terry Pratchett and/or Neil Gaimen (as they coauthored, and I have no idea which came up with this) in Good Omens:

NOTE FOR YOUNG PEOPLE AND AMERICANS: One shilling = Five Pee. It helps to understand the antique finances of the Witchfinder Army if you know the original British monetary system:

Two farthings = One Ha'penny. Two ha'pennies = One Penny. Three pennies = A Thrupenny Bit. Two Thrupences = A Sixpence. Two Sixpences = One Shilling, or Bob. Two Bob = A Florin. One Florin and one Sixpence = Half a Crown. Four Half Crowns = Ten Bob Note. Two Ten Bob Notes = One Pound (or 240 pennies). One Pound and One Shilling = One Guinea.

The British resisted decimalized currency for a long time because they thought it was too complicated.

Re:Canadiana

[canowhoopass.com]

> In Canada, it's illegal to pay for any good or service, with more than 25 of any given denomination.

What he's talking about can be found in Section 8 of the Currency Act [justice.gc.ca].

Basically it is a no-nuisance law to stop people from doing things like pay fines using pennies. It doesn't say the money can be confiscated...

Many businesses will still except coins if they have been rolled. I know I have paid for movie tickes and extra value meals with rolls of nickles and dimes.

From the statute:

(2) A payment in coins referred to in subsection (1) is a legal tender for no more than the following amounts for the following denominations of coins:

1. forty dollars if the denomination is two dollars or greater but does not exceed ten dollars;
2. twenty-five dollars if the denomination is one dollar;
3. ten dollars if the denomination is ten cents or greater but less than one dollar;
4. five dollars if the denomination is five cents; and
5. twenty-five cents if the denomination is one cent.

-
Rod (Canadian)

Re:This is why Human Interface Design is important

[omega_cubed]

Some egghead thinks "optimal" means "fewest coins returned in change, on average."

No no no. Academia don't have to think about definitions. We just define it that way.

Be seriously, RTFA, people. The important part of this result is not that 18 or 83 cent recommendations. The author did it in jest in reference to the phrase "What this country needs is a good five cent cigar". (cited in the footnote of the paper). Just wait for /. to come along and rip everything out of context.

The important part of this paper is the second half, the general analysis of methods for finding "optimal" denominations or "optimal" change returns (the first defined to minimize the number of coins returned on average, the second defined as given a set denomination, finding the best way to represent a given amount). It gives asymtotic results. It is more of a computer science excercise then anything else.

W

Re:I hate math...

[IpalindromeI]

I can't think of an example where that doesn't work in a 1,5,10,25 system

The reason you can't think of any examples in the 1,5,10,25 system is because 10 and 25 are both multiples of five. Therefore whatever you could make with a 25, you could also make with five 5s. So if you would ever have five 5s or two 5s, just use a 25 or a 10, respectively. In 1,40,41 system, 41 is not a multiple of 40 (or vice versa), so it makes finding the optimal number of coins a bit more difficult, since you have to find the optimal number of factors for your change given the different coins. In a 1,5,10,25 system, 5 is already a factor of the other important coins, so you can just count up how many 5s you'd need and then reduce that into 25s and 10s. (Of course the mind usually does it the other way round.)

I agree

[sxltrex]

Think about a store that sells DVDs. Many of the items sold are going to be priced at $19.99. Maybe some at $15.99, and maybe some at $29.99, etc., but even then you've only got 4 or 5 amounts that are going to represent a large percentage of the sales at that store. I used to be a cashier, and you learn a few of the most common totals very quickly.

Re:Instead...

[Phreakiture]

Don't you think that the addition of sales tax already solves this problem?

On untaxed items (e.g. Groceries here in New York State) your explanation makes sense, but on most items we pay a sales tax somewhere between 4 and 9 percent, depending on the county and item. It almost always requires change.

Further, if your explanation were the correct one, then gasoline would not be priced such that it is always something and 9 mils (e.g. $1.529).

5?! -Interesting +Utter Crap

[Anonymous Coward]

Cecil [straightdope.com] has the right answer instead of this complete conjecture.

Re:Instead...

[xyzzy]

I'm really sorry to say that your last sentence exactly encapsulates the US buying experience :-(. For your hypothetical $3.99 item, the price can be $4.19 (5% tax rate), $4.21 (5.5% tax rate), or ghod knows what -- sales tax in the US ranges from 0% to 8-9%, and sometimes you have state and local tax. It's really a P.I.T.A. (pain in the ass).

Re:Instead...

[simong_oz]

In Australia copper coins (1c & 2c) were taken out of circulation in 1991 (I think). So everything is rounded to a multiple of 5c. The rules for the rounding (set out by law) are:

For cash transactions:
1 & 2 cents -- rounded DOWN to the nearest 10 cents
3 & 4 cents -- rounded UP to the nearest 5 cents
6 & 7 cents -- rounded DOWN to the nearest 5 cents
8 & 9 cents -- rounded UP to the nearest 10 cents
Rounding is on the total value of the bill. Individual items should never be rounded.

And where a consumer pays by cheque, credit card or EFTPOS (electronic transaction) there is no need to round at all.

So basically you win some and you lose some, but it evens out in the end. If you're really diligent, yes you can use it to your advantage, but most people have a life instead.

Re:Or, even better ...

[simong_oz]

the rounding is only on the final payment at the till, not on individual items. And it's only for cash transactions, not electronic transactions. Sometimes it rounds in your favour, sometimes in the store's favour, but it evens out in the end. Yes, it can be manipulated to save you a cent or two here and there, but anyone doing that should probably worry about getting a life first.

optimization is no non-trivial

[pioneer]

with denominations that do not divide evenly into each other it is non-trivial to find the optimal change for a given transaction.

whereas with the US denomination (and most denominations are designed for this reason) you can use a greedy algorithm to give back change (always choose the largest coin possible, repeat) and you are guaranteed to be giving back the fewest coins.

you can prove that a greedy algorithm provides an optimal solution if the problem has optimal substructure and the greedy choice property.

To prove optimal substructure consider a collection of coins for an optimal solution, $c_1, ..., c_k$, such that $\Sigma_{i=0}^k = n$ where $n$ is the amount of money in cents to change. Assume that we remove the coin with the largest value. The remaining coins, $c_2, ..., c_k$, represent the solution to the sub problem of changing $(n - c_1)$. If $c_2, ..., c_k$ is not optimal there exists another set of coins for this subproblem, $x_2, ..., x_k$, such that this solution has fewer coins. However this is a contradiction because we can now form a solution for the original problem, $n$, by combining $c_1$ with $x_2, ..., x_k$ that has a smaller size than the original optimal problem. This is a contradiction and hence $c_2, ..., c_k$ is an optimal answer to the subproblem and therefore the coin changing problem exhibits optimal substructure.

To prove the greedy choice property we must show that a globally optimal solution can be arrived at by making a locally optimal, this is, greedy, choice.

For this particular set of American denominations we can prove the greedy property with a proof by contradiction. If the greedy choice were not optimal there would be an optimal collection such that:

1. some set of dimes, nickels, pennies added to more than 25 cents or

2. some set of nickels, pennies added to more than 10 cents or

3. some set of pennies added to more than 5 cents

However, all of these situations are impossible. If some set of pennies add to more than 5 cents, simply replace 5 pennies with a nickel (the greedy algorithm is better). If some set of nickel and pennies add to more than 10 cents and if there are two nickels, replace them with a dime; If there are a nickel and the rest pennies,
replace a nickel and 5 pennies with a dime. The same holds for a quarter. If three dimes, replace it with a quarter and a nickel. If it's two dimes and nickel/pennies, replace it with a quarter. And so on... The property of the coins that results in the greedy property is that each coin denomination divides evenly into the next larger coin denomination. Therefore each larger coin denomination that is removed must be replaced by at least two additional coins.

With non-even denominations you are required to actually search an n^2 space for the correct set of denominations. in fact, the algorithm is:

$C(n) = 1 + min \{C(n-d_1), C(n-d_2), ..., C(n-d_k)\}$.

Additionally, $C(n) = 0$ for $n = 0$. We can ignore $n 0$ are we just define $C(n 0) = \infty$. By building the array in time/size $\Theta(nk)$, and keeping track at each step which value of was chosen for the minimum, then we can list the coins by tracing backwards through these recorded values. This augmentation takes no additional time since it can be done during building the array in time $\Theta(1)$.

So, basically you've changed the problem from a linear time algorithm in the amount of change to a quadratic time algorithm in the amount of change...

GOOD LUCK WALMART EMPLOYEES!

Re:Pirates

[Martin Blank]

Almost. The piece of eight (the Spanish Milled Dollar, worth eight reales) was one of the principal coins of the colonies, but the coin was not broken up. Instead, coins of values equivalent to one-half, one-quarter, and one-eighth of a dollar. One piece of eight was worth on real, eight reales to a dollar...

And now you know.

Re:Minimize coins in pocket

[Obiwan Kenobi]

The tellers come up with the most creative combinations that minimize my number of coins (and maximize theirs - this is in both of our interest).

Just as a note here, its probably not in their best interest to get back as many coins as possible.

I used to admin at a bank, and you are charged for "coin." This means the more you bring in which is unsorted, the more you are charged.

Of course, if they roll their coin then this is not a problem.

However, it would cost them more if they try to maximize their coin input without rolling.

Also, this is probably the most nit-picky post in my history of posting. God help us all.

Re:Pirates

[uberdave]

This site [espd.com], and Item 17 on this [midtenrelics.com] webpage would seem to cast some doubt on your objection.

Due to a chronic shortage of "small change" throughout America's colonial period, the practice of cutting quarter, half and whole Spanish dollars into "bits" was commonplace.

Once smaller silver coins became widely available during the 1800's, the crudely cut pieces of eight were melted down into silver bullion or exchanged for newly minted coins. Coin collectors of the period apparently showed little interest in collecting cut pieces of eight since the date and other identifying characteristics were often missing. Consequently, most surviving examples of this American tradition are generally found only at archeological sites.

Re:$0.99?

[mark-t]

Contrary to popular belief, the common pricing structure of $something.99 was not tied directly to retailers trying to make something sound less expensive than it really was.

The origins of the pricing structure used date back to when the first cash registers were invented, that could print receipts for the company's own records (this was before the policy of giving a customer a receipt as well had been adopted). By using this sort of pricing, it was anticipated that the customer would probably be expecting change, and so the person operating the till would have to enter the transaction into the cash register in order to get the till drawer to open to collect the change. With a record of the transaction stored on a roll of paper inside the machine, the person operating the register could not simply pocket the money without being caught by the owner when the till contents was counted. By having the large, easily read numerals on the pop-up tabs on the register in plain view of the customer, a customer with nothing more than basic ciphering skills could easily and independantly calculate whether or not they would be getting back the correct amount of change, and could often be trusted to complain quite loudly if the person using the till did not give them back what they expected.

Re: Penny minting - Inflation?

[js7a]

Eliminating the penny just makes sense [coincoalition.org].

Re:18, it's a magic number.

[muon1183]

Regarding the ancient, mystic aspect of your post, I think I can explain the history behind this some. In the old hebrew counting system, the leters were used for numbers (but it was decimal, it's just that they used letters instead of the current notation), and the letters for 18 spelled out the word for life. Hence, 18 was (and still is by some people) considered lucky.