Make $5 Using One of Each CoinDate: 07/07/2001 at 14:01:21 From: Steve Thur Subject: 100 coins = $5 dollars, use 1 of each coins Dr. Math, My teacher asked my class to find solutions for this problem: You have 100 coins: pennies, nickels, dimes, quarters, and half dollars. Use at least one of each to add up to $5.00. Can you help? Steve Date: 07/09/2001 at 16:33:50 From: Doctor Greenie Subject: Re: 100 coins = $5 dollars, use 1 of each coins Hi Steve - Here are what I think are the two keys to going about finding solutions to almost any problem involving making certain total amounts using certain numbers of pennies, nickels, dimes, quarters, and half dollars: (1) Because any total amount (in cents) using only nickels, dimes, quarters, and half dollars is a multiple of 5, the desired total for a particular problem limits the possible numbers of pennies. If the desired total is $2.53, then the number of pennies must be one of the numbers 3, 8, 13, 18, ..., 248, 253. In your problem, the desired total is $5.00, or 500 cents; you also have the restrictions that there is at least one penny and that there are 100 coins in all. So the number of pennies must be one of the numbers 5, 10, 15, ..., 85, 90, 95. (2) Given n coins that are all nickels and/or dimes, you can make any total number of cents that is a multiple of 5 between 5n (all nickels) and 10n (all dimes). For example, with 4 nickels and/or dimes, you can make any total that is a multiple of 5 between 5*4 = 20 cents and 10*4 = 40 cents: dimes nickels cents ----------------------- 0 4 20 1 3 25 2 2 30 3 1 35 4 0 40 In your problem, you have the restriction that there must be at least one of each type of coin. This means that with n coins that are all nickels and/or dimes (with at least one of each), you can make any total number of cents that is more than 5n and less than 10n. Using these two facts, you can search for solutions to your problem as follows: (1) Arbitrarily choose the numbers of half dollars and quarters you want to try. (2) For that combination of half dollars and quarters, consider all the possible numbers of pennies you could have. (3) For each combination of half dollars, quarters, and pennies you have, determine (a) the number n of remaining coins (nickels and dimes) and (b) the remaining number c of cents required to achieve the total of $5.00. If the remaining cents required, c, is more than 5 times n and less than 5 times n, then the combination will work. (You will still have some work to do to determine the numbers of nickels and dimes... but you know there will be a solution.) Here is a table of the results of this process assuming an initial guess of 2 half dollars and 6 quarters: column 1: number of half dollars column 2: number of quarters column 3: number of pennies column 4: total number of half dollars, quarters, and pennies column 5: total amount using half dollars, quarters, and pennies column 6: remaining number of coins (nickels and/or dimes) column 7: remaining amount using nickels and/or dimes column 8: can this remaining number of cents (column 7) be made using the remaining number of coins (column 6) if there is at least one nickel and at least one dime? In other words, is the number in column 7 more than 5 times the number in column 6 and less than 10 times the number in column 6? column 9: solution (half dollars, quarters, dimes, nickels, pennies) (1) (2) (3) (4) (5) (6) (7) (8) (9) -------------------------------------------------------------------- 2 6 5 13 $2.55 87 $2.45 no 2 6 10 18 $2.60 82 $2.40 no 2 6 15 23 $2.65 77 $2.35 no 2 6 20 28 $2.70 72 $2.30 no 2 6 25 33 $2.75 67 $2.25 no 2 6 30 38 $2.80 62 $2.20 no 2 6 35 43 $2.85 57 $2.15 no 2 6 40 48 $2.90 52 $2.10 no 2 6 45 53 $2.95 47 $2.05 no 2 6 50 58 $3.00 42 $2.00 no 2 6 55 63 $3.05 37 $1.95 yes (2, 6, 2, 35, 55) 2 6 60 68 $3.10 32 $1.90 yes (2, 6, 6, 26, 60) 2 6 65 73 $3.15 27 $1.85 yes (2, 6, 10, 17, 65) 2 6 70 78 $3.20 22 $1.80 yes (2, 6, 14, 8, 70) 2 6 75 83 $3.25 17 $1.75 no 2 6 80 88 $3.30 12 $1.70 no 2 6 85 93 $3.35 7 $1.65 no 2 6 90 98 $3.40 2 $1.60 no You can make similar tables for any initial guess for the numbers of half dollars and quarters. Having some extra time to play around with this, I made an exhaustive analysis of this problem and found 177 different ways to make change for $5 using 100 coins. (However, I could easily have made a simple arithmetic mistake or two along the way, so that may not be the correct number of solutions...) - Doctor Greenie, 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/