cancel
Showing results for 
Search instead for 
Did you mean: 
cancel
Showing results for 
Search instead for 
Did you mean: 

Making change for a dollar.

Making change for a dollar.

My mother was posed a question that read roughly as "How many ways are there to make change for a dollar?" The only coins are the penny, nickel, dime, and quarter. Others working with her used the good old pencil and paper approach and tried listing all combinations. Here is a much simpler way that can avoid a lot of the work. It is based on a computer science technique known as "linear programming."

At each step, keep track of how many ways there are to make change for each amount up to 100. (100 cents to a dollar).
Start with the quarter.
0 : 1
25 : 1
50 : 1
75 : 1
100 : 1

Now, go through with the dime. For each entry above, add that quantity to monetary amount 10 cents greater. (Ie, that larger quantity can be obtained in the same number of ways as the entry being considered by just adding a dime.) It is important to start with "0" cents and work your way up.

0 : 1
10 : 1
20 : 1
25 : 1
30 : 1
35 : 1
40 : 1
45 : 1
50 : 2
55 : 1
60 : 2
65 : 1
70 : 2
75 : 2
80 : 2
85 : 2
90 : 2
95 : 2
100 : 3

What this means is that there is 1 way to get 40 with dimes and quarters, two ways to get 60, and three ways to get 100. Now, we do nickels.

0 : 1
5 : 1
10 : 2
15 : 2
20 : 3
25 : 4
30 : 5
35 : 6
40 : 7
45 : 8
50 : 10
55 : 11
60 : 13
65 : 14
70 : 16
75 : 18
80 : 20
85 : 22
90 : 24
95 : 26
100 : 29

Note that the numbers are building up rapidly. The next step would be to do the same to pennies. Luckily, this isn't actually necessary. The number of ways to reach 100 is the sum of all of those (since any way you can reach, say, 45, can be made into a unique combination of 100 by adding 55 pennies.) Thus, in general, you can find out the solution for ANY number 1-100 by adding up the numbers less or equal to it.

1 + 1 + 2 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 10 + 11 + 13 + 14 + 16 + 18 + 20 + 22 + 24 + 26 + 29 = 242

Thus, there are 242 combinations. I did tremendously less work than I would have enumerating all combinations. I have used this technique to treat quantities as high as a million dollars (using a computer of course). This would have been impossible had I tried listing all combinations.

Craig
3 REPLIES 3

Making change for a dollar.

�Change� problems are classic in combinatorial mathematics. Using this generating polynomial,
.
we find that the coefficient of x100 is indeed 242. The coefficient of x53 is 49, so there are 49 ways to make 53cents using pennies, nickels, dimes and quarters. Using MathCad or StudyWorks we can collect the coefficients of the polynomial.
May I suggest a wonderful little book: Mathematics of Choice by Ivan Niven. The book is part of The Mathematical Association of America, New Mathematical Library.


https://enterprise.maa.org/ecomtpro/Timssnet/products/TNT_products.cfm



PKA

Making change for a dollar.

I have seen the polynomial before. However, it is really just a fancy way of rewriting the original problem. Expanding it is also no easier to calculate than the original problem. Substituting a "sufficiently large" value for x is even worse. I see no way the use of such a polynomial can aid in computation by humans or by computers. A closed form solution, however, would be interesting to see. Tests suggest such a formula probably exists. For powers of ten, an obvious pattern emerges after the first vew powers.

The simple method illustrated initially takes O(r n) steps, where "r" is the number of coins and "n" is the number of cents for which change is sought. Moreover, the results for all amounts of change up to n can be obtained at the same time at no additional cost.

If "x" is replaced by a constant with "b" bits (or digits), and multiplication is performed, O(r n b log(n b)) is a fair estimate.

Expanding the polynomial (using convolution and FFT) would be about O(r n log n). Retrieving only the coefficient needed would take O(r n) as well, but the constant would be a bit larger.

Note: O(n^2), for example, means that the time required to compute grows no faster than the square of the size of the input. If the input doubles, the time required might quadruple.

The nice part about a closed form solution is that the output may be calculated very quickly.

Craig

Making change for a dollar.

is that book that good, dr. alford?

do u think "what is calculus about" by ww sawyer is good?
Announcements
Check out the latest
Mathcad Tip
"PTC Mathcad 15 / Prime 1-6 Update."