Hello, dear reader! If you are a new reader, welcome! (I know there is at least one of you—thanks to commenter sg211 for prompting me to post again. =)
I must apologize for dropping the ball on writing up the solution to part II of the powers of two challenge from a couple months ago, and in a broader sense wrapping up my ongoing series on Recounting the Rationals. One reader even wrote me an e-mail with a friendly reminder to write up the solution! Well, I haven’t forgotten about it, and I promise to get to it soon.
In the meantime, here’s an interesting problem for you. I have a little clear plastic piano-shaped thing that sorts US coins—you put coins in the top, and it sorts them into stacks by type. I went to put some coins in the other day and noticed that there were a ton of quarters in it, but almost no nickels, which made me wonder whether there was a reason for that, or whether it was just some sort of fluke. So, the question for you is: was it a fluke? Or would you expect me to have fewer nickels than quarters in my coin-sorting piano?
[For any non-US readers who don’t know, the values of US coins are 25 (quarters), 10 (dimes), 5 (nickels), and 1 cents (pennies). Actually, there are also coins worth 50 (half-dollar) and 100 cents (dollar), but those are far less common.]
To be a little more precise, you can make the following assumptions, all of which are, of course, completely false in the real world, but hey, this is a math problem. =)
- I started with a completely empty coin-sorting piano.
- I never use any coins in making purchases, but always pay with bills only.
- The cents portion of the prices of things that I buy are random and uniformly distributed between 0 and 99; in other words, for any particular number n between 0 and 99, there is a 1/100 chance that the price of something I buy will be some number of dollars plus exactly n cents.
- Cashiers always give me change in quarters, dimes, nickels, and pennies (no dollars or half-dollar coins), using the fewest number of coins possible. (For example if I am owed 16 cents in change, I would get one dime, one nickel, and one penny, not three nickels and a penny or anything like that.)
As usual, post comments, questions, and/or solutions in the comments (don’t peek if you haven’t tried solving it first! =)
The Math Less Traveled 
I would expect, given those conditions, to get an average of 2 pennies, 0.4 nickels, 0.8 dimes, and 1.5 quarters per transaction. So I’d very much expect to see many more quarters than nickels or dimes, but more pennies than quarters.
Here’s how I got that:
For change values from 0-24 cents, you get no quarters. From 25-49 cents, 1 quarter; from 50-74, 2 quarters, and from 75-99, 3 quarters. Over a course of 100 transactions, I’d expect to see 25*0+25*1+25*2+25*3 or 150 quarters, averaging 1.5 per transaction.
Looking at 0-24 cents, you get 1 dime for 10-19, and 2 dimes for 20-24, so for 25 transactions, you’d get, on average 1*10+2*5 or 20 dimes, or 0.8 per transaction. Above 24 cents, you’d get one or more quarters out of it, which reduces it to this case.
Again, looking at 0-24 cents, you’d get 1 nickel for transactions in the 5-9 cent and 15-19 cent ranges, so for 25 transactions you’d get 10 nickels, or 0.4 nickels per transaction. Above 24 cents, quarters will come out reducing things to 0-24 again.
You only have to look at 0-4 cents for pennies. Greater than 4 cents, and nickels, dimes, and quarters come out, reducing it to 0-4 cents. Over 5 transactions, you get 10 pennies, for 2 pennies per transaction.
I think I agree with Blaise. But this puzzle isn’t as complicated as it could be. I haven’t actually checked it rigorously, but the US coin system seems to have the following property:
When giving you change, the cashier should start with the biggest coin and give you as many as possible without giving you too much change; then they should move to the next-biggest coin and do the same; and so on, until they’ve given you as many pennies as necessary to give you all the change you need.
I think Blaise assumes the US coin system has this property (as I did when I was trying to solve it). What if the coin system didn’t have this property? What if (for example) we had only coins of values 1, 3, and 4? Suppose the cashier wanted to give you 6 cents change. If they followed my greedy strategy, then they would give you a 4-cent coin and then two 1-cent coins: 3 coins in total. But you specified that they should give you the fewest number of coins possible, so they should have given you two 3-cent coins instead.
A different set of coin-values would make this problem harder, I think.
Yes, with a (25,10,5,1) system, relative frequencies of coins should be 15:8:4:20, with a max-to-min ratio of 20/4=5 (exactly pennies to nickels, what you noticed). “Real” system (50,25,10,5,1) just lowers the frequency of quarters, and has the same max-to-min ratio of frequencies.
In Croatia, we have a (50,20,10,5,2,1) system, which gives much more balanced frequencies 5:8:4:5:8:4, with a max-to-min ratio of 8/4=2 (of course, at the expense of having a greater number of denominations).
Other countries? And as a purely mathematical puzzle, is there a system of between 3 and 98 denominations that has all the expected frequencies the same? (An example with 2 denominations is (10,1).)
Who am I to argue with the great French philosopher and mathematician, Pascal. He has correctly calculated the amounts for the problem as described, but that is a textbook problem.
What if we wanted to reflect real life.. What if you really did pay with bills for every purchase, and pocket the change? What would a pocket full of change look like at the end of the day. Remember, it is not the individual prices that matter, but the total for a checkout. Two items that end in .69 and .49 would not produce the same change as individual purchases.
Now that seems like a worthy problem. In real life, Yes, Barbie, Math is Hard
About a year ago I calculated the “density of money”, which basically has the analysis that “blaisepascal” gave. I was trying to compute the density of money in, say, dollars per kilogram, because I knew the approximate weight of a jar of coins I had and I wanted to know how much money was in there.
If I remember correctly, when I did cash in that jar of change, the ratios came out to be pretty close to the expected ones except I didn’t have as many quarters as one would expect from the random model. But that makes sense, given my change-usage patterns — I do my laundry at a laundromat, and the machines take quarters.
Tim and Pat suggest two interesting ways of generalizing the problem:
One (by Tim) is to assume that the “greedy” strategy for making change does not guarantee a (unique) minimum number of coins. If the way of making change with a minimum number of coins was always unique (but not necessarily greedy) then one could still tally the number of each type of coin one would get in 100 transactions to get the coin ratios. The problem gets considerably more interesting if the minimum number of coins wasn’t necessarily unique. Imagine, for instance, having a 2.5 cent coin (a ha’nickel) instead of a 5 cent nickel. In that case the minimal number of coins for 30 cents change is 3 — either as a quarter and two ha’nickels, or as three dimes. The end-of-day ratio of dimes to ha’nickels depends greatly on which form cashiers choose.
Pat suggested that (effectively) we should look at non-uniform distributions of purchase prices, to better model the real world. Once we settle on a distribution, however, the ratios can be gotten through enumeration (again).
This reminds me of a paper by Prof. Jeffrey Shallit, at the University of Waterloo, about the optimal denominations, concluding that the Canadian (and American) systems would most benefit from an additional 18- or 83-cent coin.
Click to access change2.pdf
Is that why the British system doesn’t use round numbers?
Steve: the UK uses the same (50, 20, 10, 5, 2, 1) system that Veky tells us Croatia uses (as well as one- and two-pound coins—i.e. 100 and 200).
Prior to decimalization in 1971, things were more interesting: a pound was 20 shillings, and a shilling was 12 pence. The coins available were (30, 24, 12, 6, 3, 1, 1/2). Earlier, there were other coins, too, like the farthing (1/4 of a penny) and the guinea, whose value varied with the price of gold. When the actual coin dropped out of circulation, the word “guinea” came to mean 21 shillings—a sort of pound on steroids.
Depending on what you mean by “round”, the old British system actually did have quite round ratios. For example, the ratio of the half-crown (30 pence) to the halfpenny was 60:1. The factors of 60 are 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, and 60, but the number 100 has fewer factors (1, 2, 4, 5, 10, 20, 25, 50, 100), even though it’s a larger number.
Okay. It was none other than Brent himself who told me there were awkward ratios. But he was about half as old then as now.
Alright, this is the first problem here I’ve seen in a while that seems attainable to me, and I’m sure it’s been solved in a comment above but I’m skipping what all y’all wrote so I can try this. I am sure it will take longer than I want it to.
Well, first thing I notice is that four out of every five prices should give you at least one penny. And I can get more specific:
20% of purchases -> 0 pennies
20% of purchases -> 1 penny
20% of purchases -> 2 pennies
20% of purchases -> 3 pennies
20% of purchases -> 4 pennies
I wonder if the idea of an expected result helps? I want to calculate an expected number of pennies I’d get on a single purchase:
.2*1+.2*2+.2*3+.2*4 = 2 pennies.
I could well have gone about that the wrong way as we’re already beyond my level of knowledge here, but moving on.
The next easiest thing for me to calculate is how many quarters I expect to see.
25% of purchases -> 0 quarters
25% of purchases -> 1 quarters
25% of purchases -> 2 quarters
25% of purchases -> 3 quarters
So on any given purchase I expect 1.5 quarters.
I have to think more about dimes and nickels but it can’t be too hard. What can I do to avoid using brute force, which I know is not very sexy in the math world? Well, I only need to think about the first quarter of 100 now, because when we reach 25 we’ll start repeating. So within that first quarter, we’ll have 0 dimes on 0-9, 1 dime on 10-19, and 2 dimes on 20-24. I think that equates to
40% of purchases -> 0 dimes
40% of purchases -> 1 dime
20% of purchases -> 2 dimes
So I expect .8 dimes per purchase.
Since any time I would get two nickels I’d get a dime instead, I will always get back exactly 0 or 1 nickel. Again, I think I can think within just the span on one quarter of a dollar, since it does not matter to me if the nickel adds in to make a number ending in 0 or a number ending in 5, so long as it happens regularly. So, within the first quarter, I will only see nickels from 5-9 and 15-19, won’t I? That’s 10/25, or just 40% of the time that I get a nickel! Poor nickel. So I expect .4 nickels per purchase.
I am a little surprised to find that it does look like quarters should be pretty common, but not all all surprised that pennies edge them out.
Under your premises, we should accumulate quarters:dimes:nickels:pennies at a 15:8:4:20 ratio! I hope I’m right . . .
There is a much more important conclusion here: Brent has not done his laundry in far too long.
Jonathan: hehe, actually, we have a non-coin-operated washer and dryer. =)
Well then you and the lady should go to an arcade and bond over some air hockey.
Don’t tempt me, Brent, I can suggest a lot of uses for quarters.
Hi! I programmed an attractive online calculator that find the greatest common divisor(GCD) between two numbers. I will be happy, if you add the link in your blog. I hope that you and your visitors will enjoy!
—
http://gcd.awardspace.com
—
bye!
Pingback: Optimal change-carrying « The Math Less Traveled
I am baffled here. I habitually pay for everything with bills, and save all change in a bucket for a year or more. The last time I counted the coins in the bucket, it occurred to me that you should be able to estimate the ratios between the denominations pretty closely, and when I calculated the theoretical ratios as above, the actual ratios in the bucket were very close. And I was happy.
But this time not so. The ratio of dimes to nickels in the bucket this time is almost exactly 2:1 as calculated. And the ratio of pennies to quarters is almost exactly 4:3, also as calculated. But the number of quarters is only slightly higher than the number of dimes. So the ratio of pennies to dimes is about 3:2 instead of the calculated 5:2. I have struggled to come up with an adjusted set of assumptions that might explain this anomaly, but have been unable to do so. Can anybody help me here?
Thanks in advance.