Ideal Coin Value Choices

Backstory: Someone asked a group what they thought his 16 pounds of pennies, nickels, and dimes turned out to be worth when he took them to CoinStar (minus the 10% "processing fee"). Using published coin weights--and the U.S. statistics of coin manufacture as an approximation for "coins in the wild" (assuming a competent minting authority would pick the right ratios to match average change amounts, which vary but average about 5:1:2), I guessed 108 dollars. The actual value was 111.77, so a pretty darn good guess if you ask me!

Anyway... Beyond gloating about my estimate being the closest one :-) this reminded me of a problem I'd speculated about when I was a kid. It was about ideal choices for coin values. I assumed change to be computed with machines, so that you need not be concerned about conveniences for five-fingers-per-hand beings or base-10.

Here's how I'd "formalize" my musing today, now that I know a bit 'mo math:

• There is a "paper bill" radix R, for which you do not have to be concerned about making coins. (In the human US system this is 100, of course.)

• There is a probability function of price endings for cash transactions P, over the domain of integers between (0...R-1) which sums to 1.0

• Call the number of distinct coin values N. This can range from 1 ("only pennies") to R-2 ("all 'change' can be made using a single coin")

• There's a cost function C over the domain of N for the cost of manufacture of each coin

• There is a probability of being lost or misplaced over a period of time T as function L over the domain of N

Clearly this is simplified if we go with the youthful assumptions I made way-back-when:

• P(n) is constant

• C(n) is constant

• L(n) is zero

I didn't imagine otherwise until reading up on the hairy practicalities while solving my friend's 16-pound-o-change challenge. (!)

There are a few minimization problems to solve here. The "most real" one is probably the one from the mint's perspective, to make the number of coins in distribution as small as possible (or rather, to make their yearly cost as low as possible). The one I was originally thinking about was how to stabilize or minimize the quantity of coins in cash registers and pockets.

I mention all the gritty details just because they interest me. But let's say this question is about the "simple" scenario:

A manufacturing distribution function M over (R,N) that minimizes total coin count.

It seems there'd be an article about this on the web somewhere, but my searches on "ideal coin" always seemed to take the 1, 5, 10, 25, etc. for granted. :-/

-
In the "obviousness department": M(R,R-2) is uniformly 1.0/(R-2) and M(R,1) is simply 1.0. –  HostileFork May 31 '12 at 19:55
I'm pretty sure the manufacturing-distribution function together with your other assumptions are not sufficient data to predict the "total coin count" you want to minimize. For one thing, the ease of handling of each type of coin influences the demand. For example, suppose there's a quarter-dollar of ordinary coin size, and a half-dollar that's slightly too large to fit well in a typical cash drawer. Then retailers would not stock any half-dollars to use as change, preferring to give out two quarters, so almost no half-dollars would ever enter circulation. But your parameters can't see that. –  Henning Makholm May 31 '12 at 20:14
@HenningMakholm Good point on the size being a fairly big deal... I found some articles on the history of coin sizes. (Obviously the materials used influence the size, but one might ask why larger coins weren't designed/chosen to be the more valuable ones.) Still, it factors into the loss rate function... –  HostileFork May 31 '12 at 20:24

A not-entirely-unrelated problem is Minimum set of US coins to count each prime number less than 100, where we learn that if we have three quarters, two dimes, a nickel, and four pennies --- ten coins, in all --- we can make any amount up to 100, and we can't do that with fewer than ten coins, if we are restricted to quarters, dimes, nickels, and pennies. Well, the problem actually looks at prime amounts, but it's easy to see you can get any amount up to a dollar (indeed, any amount up to \$1.04). So if the US Mint makes coins in the ratio 3 to 2 to 1 to 4, US residents can all go around with ten coins and be confident of being able to make at least one exact payment a day. If they changed denominations to 1, 2, 4, 8, 16, 32, and 64 cent coins --- nice round numbers in binary, those --- then residents would only need seven coins to make all exact payments up to (but not including) one binary dollar (=\$1.28).