Making Change
July 19, 2013
As a student of
solid state physics, I was introduced to the many ways that quantum mechanics has been applied to solids. The isolated hydrogen atom is typically presented as the model system for quantum mechanics, since its energy levels are relatively easy to calculate, and they agree marvelously with experimental spectral measurements.
When you combine hydrogen atoms into something that actually exists in nature, hydrogen molecules (H2), things get a little harder. When you combine many atoms of different types into a solid, it's nearly time to put away the books and take up gardening.
Fortunately, most solids are not a jumbled mass of atoms or molecules, they're crystals in which the atoms are arranged in spatial order. This gives the theorist another way to do his quantum calculations; and, in the first few decades after World War II, the quantum theory of crystals was developed to the point where the performance of semiconductor devices could be predicted and improved. Hans Bethe was ahead of the curve with his 1929 article, Termaufspaltung in Kristallen (Splitting of Terms in Crystals), which appeared in the Annalen der Physik.[1]
Electrical conductance in semiconductors, such as the silicon that comprises most transistors, is explained by electronic band theory in which electrons can exist in certain states, but not others. One such band is the valence band of states that glues the crystal together, and these electrons are too busy doing this to do anything else.
Higher in energy are the conduction electrons with energy states so dense that they form a conduction energy band. In a semiconductor, there's a forbidden range of energies between the valence and conduction bands, and electrons need an energy boost greater than this gap to be promoted from the valence band to the conduction band. That's why the electrical conductivity of semiconductors increases with temperature, since thermal forces are putting more electrons into a conduction role.
At the time I learned all this, sales taxes were just becoming popular (or notorious) as a means of generating government income. I realized that there was an analogy between item prices with sales tax and forbidden energy levels, as follows. Before sales tax, I could buy an item for 99 cents ($0.99). According to the sales tax rule at the time, I needed to pay $1.00 for that item; that is, 99 cents had become a forbidden price. It was impossible to buy something for ninety-nine cents.
This leads to another interesting problem. If it were possible to pay 99 cents for an item, how many different ways could you do this? Using common US coinage in which fifty cent pieces are now rare, the method using the least number of coins would be three quarters, two dimes, and four pennies, for a total of nine coins. The least efficient way, of course, is 99 pennies. In between, there's a wide spectrum of possible coins.
Computationally, you could enumerate the number of ways by starting with the coin set {25,25,25,10,10,1,1,1,1}, then breaking down each member individually into smaller coins; thus, the next coin set would be {10,10,5,25,25,10,10,1,1,1,1}, etc. Since this is a simple enough computer program, I tackled it with the attached source code in my casual coding style.
It would be just as easy to enumerate these by hand, since it's a simple tree. There are 31 possible coin combinations to render $0.99. Here are a few of the smallest. We first split the 25-cent pieces into dimes and nickels, then the dimes into nickels, and the nickels into pennies.
{25,25,25,10,10,1,1,1,1}
{10,10,5,25,25,10,10,1,1,1,1}
{10,10,5,10,10,5,25,10,10,1,1,1,1}
{10,10,5,10,10,5,10,10,5,10,10,1,1,1,1}
{5,5,10,5,10,10,5,10,10,5,10,10,1,1,1,1}
{5,5,5,5,5,10,10,5,10,10,5,10,10,1,1,1,1}
{5,5,5,5,5,5,5,10,5,10,10,5,10,10,1,1,1,1}
{5,5,5,5,5,5,5,5,5,5,10,10,5,10,10,1,1,1,1}
{5,5,5,5,5,5,5,5,5,5,5,5,10,5,10,10,1,1,1,1}
{5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,10,10,1,1,1,1}
{5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,10,1,1,1,1}
{5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,1,1,1,1}
...etc., for 31 total combinations.
In the cold weather months, I'll usually have change for any fractional part of a dollar, since my coats have large pockets in which I carry a lot of coins. In that case, I'm just like an athlete who wears training weights. I've never examined the distribution of coins in my coin stash, but I'm sure that it would follow some statistical rule.
Two mathematicians have posted a paper on arXiv to answer the question "What set of coins is most likely to be the contents of your wallet?" They are Lara Pudwell of the Department of Mathematics and Computer Science, Valparaiso University (Valparaiso, Indiana) and Eric Rowland of the Laboratoire de combinatoire et d'informatique mathématique, Université du Québec à Montréal (Montreal, Canada).[2-3]
Their calculation was a little more involved than my simple program, since they looked at all ways that fractional parts of a dollar that can be returned as change from a purchase, not just the ninety-nine cent case. Their assumptions were that there's a uniform distribution of prices between 0 and 99 cents and cashiers return change as the smallest number of coins. As in my example, half-dollar coins were disallowed.
If you spend no coins, but just collect coins from all transactions under a dollar, you should have 150 quarters, 80 dimes, 40 nickels, and 200 pennies in the end. Percentage-wise, this is 31.9% quarters, 17.0% dimes, 8.5% nickels, and 42.6% pennies.[2] That calculation is also easy to do, but I've left it as an
exercise for the reader, which is what my professors and textbook authors always said.
When I was a child, I could purchase "penny candy." Now, a penny wouldn't even buy you the right to sniff a chocolate bar, since inflation has rendered pennies practically worthless. In 1982, when the copper value of a US penny was nearly a penny, the US Mint started making pennies which are 97.5% zinc with a 2.5% copper plating. Still, the manufacturing and distribution cost of a US penny is about two cents.[4]
People don't usually carry pennies, and they drop them into the popular give-a-penny/take-a-penny cups at cashiers. So, these shoppers are "pennyless," as distinct from "penniless," and they require a different analysis. The following table shows the ten most likely wallet states for the pennyless purchaser. Note that even the most probable state, that of an empty wallet, has just a five percent likelihood.
State | Probability | | State | Probability |
{empty} | .05000 | | {10, 5, 5} | .02731 |
{5} | .05000 | | {25, 25, 10, 5} | .02625 |
{10, 5} | .03916 | | {5, 5} | .02536 |
{25, 10, 5} | .03093 | | {10} | .02463 |
{25, 5} | .02847 | | {25, 10, 5, 5} | .02417 |
For those of us who aren't pennyless, the following statistics apply to our wallets, assuming that we carry less than a dollar in coins.[2]
• There should be ten coins.
• The probability that there is at least one nickel is 0.58085.
• The probability that there is at least one penny is 0.95975.
• The probability of there being only pennies, if you have any coins at all, is 0.08430.
• The probability of having an empty wallet is .01000.
• The probability of having the exact change is only 0.00831.
• The expected number of quarters is 1.06.
• The expected number of dimes is 1.15.
• The expected number of nickels is 0.91.
• The expected number of pennies is 6.92.
My cold weather pockets contain enough in coins that I always have exact change. I suspect that keeping about two dollars in coins, perhaps
weighted on the penny side (in more ways than one), is enough to ensure that fact.
Pudwell and Rowland also calculate the approximate distribution of circulating coins as 10.5% quarters, 11.5% dimes, 9.1% nickels, and 68.9% pennies. The distribution of U.S. minted coins in 2012 is actually 6.1% quarters, 18.1% dimes, 11.0% nickels, and 64.8% pennies.[2] Not bad for an ab initio calculation.
The statistics might be skewed, slightly, by people who hoard certain coin denominations. My uncle Walt, for one reason or another, had a giant jar of pennies in his room. I think he was hoping to collect something of numismatic rarity. Evelyn Lamb admits to being a quarter-hoarder in her Scientific American blog.[3] Her reason is their utility in coin-operated laundry machines. I do the same, for road tolls, which are generally collected by automated machines in our area. I don't use E-ZPass, since I'm a "privacy nut."
References:
- H. Bethe, "Termaufspaltung in Kristallen," Annalen der Physik, vol. 395, no. 2 (1929), pp. 133-208. Translation appears in Splitting of Terms in Crystals, chap. 1 of Selected Works of Hans A. Bethe: With Commentary, (World Scientific, Jan 1, 1997), 605 pages.
- Lara Pudwell and Eric Rowland, "What's in your wallet?!" arXiv Preprint Server, June 9, 2013.
- Evelyn Lamb, "Mathematicians Predict What's in Your Wallet," Scientific American Blogs, June 20, 2013.
- Michael Zielinski, "Cost to Make Penny and Nickel Declines But Still Double Face Value," Coin Update, December 10, 2012.
- Bill Gates, The World's Billionaires (#2), Forbes, March, 2013.