Making Change for a DollarDate: 05/29/2001 at 23:39:33 From: Kathy Holman Subject: Coin problem Making change for $1.00, what is the smallest number of coins you cannot make change with? I started by: 1. one silver dollar, 2. two half dollars, 3. one half dollar and two quarters, 4. four quarters, 5. one half dollar, one quarter, two dimes and one nickel. I got up to 23 - 17 nickels, 1 dime, and 5 pennies (this equals 23 coins). Now I seem to be stuck finding the smallest number of coins you CANNOT make change with. Please help! Date: 05/30/2001 at 18:24:19 From: Doctor Greenie Subject: Re: Coin problem Hi, Kathy - This is an interesting twist to the old problem of "how many ways can you make change for a dollar?" After playing with the problem for a little while, you probably can get an idea that the number you are looking for is quite large, so let's do our search from the opposite end of the range - that is, let's look for combinations using as MANY coins as possible. If we want to use as many coins as possible, then we don't want to use half dollars or quarters. So let's look first at the numbers of coins we can use to make a total of one dollar if we use only dimes, nickels, and pennies. With no dimes, I can have from 0 to 20 nickels. With 0 nickels, I have 100 pennies. For each additional nickel, I have 5 fewer pennies, giving me 4 fewer coins total. With 20 nickels, I have no pennies, for a total of 20 coins. Here is a table of the possibilities with nickels and pennies only: dimes nickels pennies # coins -------------------------------- 0 0 100 100 0 1 95 96 0 2 90 92 0 ... ... ... 0 19 5 24 0 20 0 20 So with 0 dimes, I can have any number of coins between 20 and 100 that is a multiple of 4. Now let's consider the possibilities with only dimes, nickels, and pennies when I have exactly 1 dime. With 1 dime, I can have from 0 to 18 nickels. With 0 nickels, I have 90 pennies, for a total of 91 coins. As before, for each additional nickel I have 5 fewer pennies, giving me 4 fewer coins total. With 18 nickels, I have no pennies, for a total of 19 coins. Here is a table of the possibilities with dimes, nickels, and pennies only, and with exactly 1 dime: dimes nickels pennies # coins -------------------------------- 1 0 90 91 1 1 85 87 1 2 80 83 1 ... ... ... 1 17 5 22 1 18 0 19 So with 1 dime, I can have any number of coins between 19 and 91 that is 3 more than a multiple of 4. I won't continue with the detailed analysis for the different numbers of dimes. The results of those analyses show that I can make a total of one dollar using the following numbers of coins: number different total numbers of coins using this number of of dimes dimes (and no larger coins) to make a total of one dollar -------- --------------------------------------------------------- 0 20, 24, 28, ..., 96, 100 1 19, 23, 27, ..., 87, 91 2 18, 22, 26, ..., 78, 82 3 17, 21, 25, ..., 69, 73 4 16, 20, 24, ..., 60, 64 5 15, 19, 23, ..., 51, 55 6 14, 18, 22, ..., 42, 46 7 13, 17, 21, ..., 33, 37 8 12, 16, 20, 24, 28 9 11, 15, 19 10 10 Combining all these results, the numbers of coins that can be used to make a total of one dollar using just pennies, nickels, and dimes are the following: (1) all numbers n, 12 <= n <= 100, of the form 4k (where k is an integer); (2) all numbers n, 11 <= n <= 91, of the form 4k+3; (3) all numbers n, 10 <= n <= 82, of the form 4k+2; and (4) all numbers n, 13 <= n <= 73, of the form 4k+1 (5) It is easy to find combinations of 1 to 9 coins that total a dollar. (6) Also, any combination of coins that has at least one coin larger than a dime will have a total of at most 76 coins. From (1) through (6), it follows that the following are the only numbers of coins with which you can NOT make a total of a dollar: ==> all numbers n, n > 91, of the form 4k+3 (95, 99) ==> all numbers n, n > 82, of the form 4k+2 (86, 90, 94, 98) ==> all numbers n, n > 73, of the form 4k+1 (77, 81, 85, 89, 93, 97) So the smallest number of coins with which you cannot make a total of a dollar (the answer to the question you asked) is 77. - 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-2013 The Math Forum
http://mathforum.org/dr.math/