Making cents
Sun Jul 25, 2010 11:29 (UTC -5)Like most Americans (citation needed), I’m a vortex from which coins rarely escape. I’m in the habit of paying for everything with bills and then throwing any change I receive into a jar once I get home. The jar fills up until I swap out the coins for paper (less 8%).
That was all fine and good for a while, but I figured that that 8% could really add up over the course of a lifetime. Rather than paying a periodic fee to maintain my current habit, I could just change my habits by—dun dun dun—spending my change. So, I decided that I should carry coins around with me. But how many? And which coins?
Whenever I go out, I usually don’t make more than one transaction, so I’d only have to be able to produce 0-99 cents. Recall for that any amount of money, there’s a minimum number of coins you can use to make it. (I’m talking about US coins here, and I’m going to assume that people only use pennies, nickels, dimes, and quarters, which is generally true.)
To make change with the fewest number of coins, you use a greedy algorithm: use as many quarters as you can without going over, then dimes, then nickels, then pennies. To make 44 cents, you would use a quarter, a dime, a nickel, and 4 pennies, for a total of 7 coins. You could also use 4 dimes and 4 pennies, or 44 pennies, but with those combinations or any others, you can’t beat 7 coins.
So, I decided to carry around only the coins necessary to make any amount from 1 to 99 cents with as few coins as possible:
- 3 quarters
- 2 dimes
- 1 nickel
- 4 pennies
I’d never been one to carry change around, but since I started doing this, I’ve realized what I’ve been missing out on. When I go out for a drive with my friends, I can actually contribute to the parking meter. Recently someone asked me to pay for her bus fare, and I was able to give the exact amount. I no longer have to decide whether to tip a waiter $2 or $3. And, for those times when I’ve run out of singles or someone just needs change for a dollar: the quarters, dimes, and nickel add up to $1.
Coincidentally, today’s links also have to do with money, although in a roundabout way.
An article about the services that come with those fancy credit cards: How to Make Visa Obey Your Every Desire… with ridiculous real-life examples! (Via The Consumerist)
From Slate: Heartwarming long-lost wallet stories happen more often than you may think. (Via Josh of mcgees.org)
9 comments
#1 by Joshua McGee: Sun Jul 25, 2010 12:06 (UTC -5)
To make change with the fewest number of coins, you use a greedy algorithm
A greedy algorithm works here, but it is a special case produced by the denominations chosen for U.S. coins. A greedy algorithm will frequently fail with the general problem. Imagine that coins (or, better, postage stamps) were available in 25¢, 14¢, and 1¢ denominations, and you had to use the minimum number for 28¢.
The general solution is much more subtle, and took me three years of conversations with professional mathematicians and computer scientists until I found a technique that works. I don’t think that there exists an algorithm in which one can be given the denominations and the target figure and then start calculating without prep work, in the way one can with the greedy algorithm.
You wanna give it a try? It is really hard, and I was not able to discover it on my own.
#2 by Jordon Kalilich: Sun Jul 25, 2010 12:12 (UTC -5)
I did realize that after reading Wikipedia’s article on greedy algorithms, and that’s why I mentioned that I’d be talking about American coins. I seem to recall the general case, applied to postage stamps, from one of my classes, but I can’t remember what the solution was.
#3 by Kirsten: Sun Jul 25, 2010 19:20 (UTC -5)
I don’t claim to understand the first thing about algorithms (except I know that I don’t understand them), but I’ve always been one to spend my change when I’m using cash. I never understood why people just toss it aside, or in a jar, or whatever.
There are other ways to keep the change from piling up. Let’s say your order comes to $4.55. You could pay with a $5 and get your 45 cents back, or you could give the cashier $4.05 and get two quarters back. If I’m going to have it be a wallet full of change, I’d want it to be made up of as many quarters as possible. They’re easier to count and are the most common coin used in vending machines, parking meters, at the laundromat, etc.
You’ll confuse many a cashier with this method because most people aren’t as mathematically inclined as you are, but it works pretty well.
#4 by Joshua McGee: Sun Jul 25, 2010 19:27 (UTC -5)
There are other ways to keep the change from piling up. Let’s say your order comes to $4.55. You could pay with a $5 and get your 45 cents back, or you could give the cashier $4.05 and get two quarters back.
I’ve met cashiers like that! They are a great way to make extra money in college!
You’ll confuse many a cashier with this method
Yeah, that’s why it works so well. :-)
#5 by Jordon Kalilich: Sun Jul 25, 2010 19:27 (UTC -5)
That’s a pretty good idea, but it seems like it would take some more getting used to. I already do a similar thing to get bills back, though. For example, if I have to pay $9.81 and I only have a $10 bill and the coins, I’ll hand over $10.81 and get a dollar bill back.
But getting specific coins back will probably come in handy once I exhaust my supply of change—which won’t be for a very long time.
#6 by Louis: Wed Feb 02, 2011 15:54 (UTC -5)
What 3 combination of coin make up 44 cents?
#7 by Jordon Kalilich: Wed Feb 02, 2011 16:54 (UTC -5)
Louis, I don’t understand your question. There are more than 3 combinations that make 44 cents.
#8 by Joshua McGee: Thu Feb 03, 2011 01:10 (UTC -5)
I’m going to have to write a program to do this, huh? Long time coming. Maybe I’ll put it on a website and put up ads that no one will click (as usual). :-)
(Jordon: First time at the site proper in a while. Ultra-classy. Going to look around this elegant design some more.)
#9 by Jordon Kalilich: Thu Feb 03, 2011 17:50 (UTC -5)
Maybe that would be a good idea!
Thanks for the comments about the design. It’s still a work in progress; let me know if you have any suggestions.