Change for a DollarDate: 11/05/1999 at 00:03:14 From: Sarah Subject: Puzzle When changing a dollar bill, you can give one coin (1 silver dollar), 2 coins (2 half-dollars), 3 coins (2 quarters and 1 half-dollar), and so on. What is the least positive number of coins that is impossible to give as change for a dollar bill? Date: 11/15/1999 at 19:23:58 From: Doctor TWE Subject: Re: Puzzle Hi Sarah - thanks for writing to Dr. Math. You ask a good question. A total of 292 combinations of coins add up to $1.00, or 293 if you count the one-dollar coin. I found this out by looking in our archives: Ways to Make Change for $1.00 http://mathforum.org/dr.math/problems/odonnell10.2.97.html Writing out all 293 possibilities would be both time-consuming and difficult. Since we're looking for the fewest number of coins, beginning with the number of coins and figuring out combinations seems like a good starting point. You found 1, 2 and 3-coin combinations. Lets continue: (I'll use H for half-dollar, Q for quarter, D for dime, N for nickel, and P for penny.) 4 coins = 4 Q 5 coins = 1 H + 1 Q + 2 D + 1 N 6 coins = 1 H + 5 D (or 2 other ways) 7 coins = 2 Q + 5 D (or 3 other ways) 8 coins = 3 Q + 5 N (or 2 other ways) 9 coins = 1 Q + 7 D + 1 N (or 3 other ways) 10 coins = 10 D (or 5 other ways) ... Gee, it seems that we're getting more and more ways instead of fewer. Let's look at it another way. For each combination that has a dime, I can exchange that dime for 2 nickels. So if there is a combination with n coins including at least 1 dime, there is a combination with n+1 coins (replacing the dime with 2 nickels). We can start with 10 D and exchange 1 D for 2 N repeatedly until we get to 20 N. That covers the combinations for 11 to 20 coins. (We already covered 1 to 10 coins, above.) Next, for every combination with at least 1 nickel, we can exchange the nickel for 5 pennies. So if there is a combination with n coins including at least 1 nickel, there is a combination with n+4 coins (replacing the nickel with 5 pennies). By continuing to exchange 1 N for 5 P and starting with 20 N, we can get 24 (19 N + 5 P), 28 (18 N + 10 P), 32 (17 N + 15 P), ..., 100 (100 P). Using the same exchange, but starting with 1 D + 18 N, we can get 23 (1 D + 17 N + 5 P), 27 (1 D + 16 N + 10 P), 31 (1 D + 15 N + 15 P), ..., 91 (1D + 90 P). Using the same exchange again, but starting with 2 D + 16 N, we can get 22 (2 D + 15 N + 5 P), 26 (2 D + 14 N + 10 P), 30 (2 D + 13 N + 15 P), ..., 82 (2D + 80 P). Using the same exchange one more time, but starting with 3 D + 14 N, we can get 21 (3 D + 13 N + 5 P), 25 (3 D + 12 N + 10 P), 29 (3 D + 11 N + 15 P), ..., 73 (3D + 70 P). Do you see why I used these combinations? By doing that, I've covered multiples of 4 with remainders of 0, 1, 2 and 3. This covers all combinations from 21 through 76 (plus a few more.) Wow! I'm glad I didn't try to eliminate them one by one! We still have to check 77, 81, 85, 86, 89, 90, 93, 94, 95, 97, 98 and 99. It turns out that all of these remaining combinations are impossible. (I checked this by writing a program that generated all 292 combinations.) Can you prove this? This was fun for me to work on, I hope you have fun working on this kind of problem, too! Here's a "bonus question" for you: how many ways can you make change for a dollar using 5 different types of coins (i.e. using at least 1 each of pennies, nickels, dimes, quarters and half dollars)? - Doctor TWE, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/