Ways to make a dollar with variable denominations

  • Thread starter soandos
  • Start date
  • Tags
    Variable
In summary: Do you get 292?In summary, the conversation discussed the knapsack problem of finding the number of ways to make change for a dollar using coins of denominations of 1, 4, 7, 15, and 33 cents each. It was mentioned that there is no easy formula for this and it requires checking every possibility. However, the book "Concrete Mathematics" by Graham, Knuth, and Patashnki provides a method using generating functions. It was also mentioned that the multinomial coefficients can be used to solve this problem. There was a discussion about using polynomials and expanding them to find the number
  • #1
soandos
166
0
How many ways are there to make a dollar using coins of denominations of 1,4,7,15,33 cents each?
is there a formula that can generalize this for any set of given denominations?
 
Mathematics news on Phys.org
  • #2
This is the knapsack problem. I doubt that there is an easy formula for this. As for your first question, I fear that you'll have to check every possibility :cry:
 
  • #3
In Graham, Knuth & Patashnki's "Concrete Mathematics" in chapter 7 shows how to use generating functions to solve problems exactly like this. Their example uses pennies, nickels, dimes, quarters and half dollars but the same steps should apply to your problem.
 
  • #4
I saw this: "Take the taylor expansion of 1 over (1-x)*(1-x5)*(1-x10)*(1-x25)*(1-x50)*(1-x100), and jot down the coefficient of x100. This is the generating function for the ways to partition 100 into subsets of size 1, 5, 10, 25, 50, or 100, so there are 293 ways to make change for one us dollar." on answers.com, but i got a massive co-efficient for the Taylor expansion about x=1.
Is this what you were talking about?
and if so, can you please explain it?
 
  • #5
It seems related to the knapsack problem, there there is no issue of weights, and the value is not to be maximized, but equal to a given number.
 
  • #6
Actually, this is also a variation on the idea of the multinomial coefficients:

when you do (a+b)^2 =a^2+2ab+b^2 , the 2 in 2ab is the number of ways

you can get a term with one a and one b in an expansion (a+b)(a+b): you

can choose the a in two ways, then the second term is determined.

Same for (a+b)^n =(a+b)(a+b)...(a+b) :

to see how many terms a^kb you can get ( 0<=k<=n, of course) : you can

select k a's out of the n possible ones in the product in nCk ways. This is

another way of seeing the binomial coefficients.

Now expand to the case of a multinomial ( x^1+x^10+...+x^25)^100

How many terms will add up to 100.?
 
  • #7
(x + x^5 + x^10 + x^25 + x^50)^100. the x^100 co-efficient is one...
unless i messed up.
 
  • #8
The description of how to understand and use generating functions in Graham, Knuth & Patashnki's "Concrete Mathematics" to solve this problem is probably too long to include here. It does show that there are 292 ways of making change for a dollar, but they do not include a dollar coin, so it is one less than your 293 ways.

If you find yourself interested in problem solving I highly recommend buying a copy of the book. There are lots of things you can learn from it. See if you can get a later edition and a later printing because, unlike Knuth's other books, there were a variety of small errors in the earlier versions of the book. There are errata lists on the net if you get an earlier version and you can go through and mark up your copy.

I only wish I could say that I had mastered a substantial fraction of all the material in the book or that I had been able to sit in the back of their class and learn the material from them.
 
Last edited:
  • #9
Some observations that may be helpful:

1. The number of ways to make change for a dollar with coins of value 1, 4, 7, 15 and 33 is the same as the number of ways to make change for a dollar or less (including an amount of zero) with coins of value 4, 7, 15 and 33.

2. If you're doing this by pencil and paper, the most efficient method may be a recursive approach. I.e., you know there can only be 0, 1, 2, or 3 coins of value 33. So find the number of ways to make change for 1, 34, 67, or 100 cents with coins of value 1, 4, 7, and 15. Keep breaking the problem into smaller cases similarly. You can probably figure out how to organize your work in a table and work from the bottom up instead of the top-down (recursive) approach.

3. If you have access to a computer algebra package, consider the polynomials
[tex]P = 1 + x^{33} + x^{67}[/tex]
[tex]Q = 1 + x^{15} + x^{30} + \dots + x^{90}[/tex]
[tex]R = 1 + x^7 + x^{14} + \dots + x^{98}[/tex]
[tex]S = 1 + x^4 + x^8 + \dots + x^{100}[/tex]
Expand PQRS. The answer to the problem is the sum of the coefficients of the powers of x less than or equal to x^100 , by Observation 1. Or you could do this with pencil and paper, retaining only powers of x less than or equal to x^100 as you go along.
 
  • #10
why is [tex]
P = 1 + x^{33} + x^{67}
[/tex]
as opposed to [tex]
P = 1 + x^{33} + x^{66}
[/tex]
?
 
  • #11
soandos said:
why is [tex]
P = 1 + x^{33} + x^{67}
[/tex]
as opposed to [tex]
P = 1 + x^{33} + x^{66}
[/tex]
?
Oops, I should have written
[tex]
P = 1 + x^{33} + x^{66} + x^{99}
[/tex]
 
  • #12
I got 824. Did i implement it correctly?
 
  • #13
Using his PQRS technique I get 823 which is the sum of 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2, 2, 2, 3, 2, 2, 3, 3, 3, 3, 4, 3, 3, 4, 4, 4, 4, 5, 5, 4, 5, 6, 6, 5, 6, 7, 6, 6, 7, 8, 7, 7, 8, 9, 8, 8, 10, 10, 9, 10, 11, 11, 10, 12, 12, 12, 12, 13, 14, 13, 14, 15, 15, 15, 16, 17, 16, 17, 18, 18, 18, 19, 20, 20, 20, 21, 22, 22, 22, 24, 24, 24, 24, 26. If you check off your coefficients against mine maybe you can find that you missed one, I missed one or we both missed something.

As a check I use his PQRS on nickels,dimes,quarters,halves and get 292 which matches the above mentioned value.
 
Last edited:
  • #14
As a check, you might find it interesting to write a program which actually generates and counts the combinations. Something like
Code:
goal = 100
nways = 0

for x33 = 0 to floor(goal / 33)
  for x15 = 0 to floor((goal - 33 * x33) / 15)
    for x7 = 0 to floor((goal - 33 * x33 - 15 * x15) / 7)
      for x4 = 0 to floor((goal - 33 * x33 - 15 * x15 - 7 *x7) / 4)
         nways = nways + 1
 

1. How can I make a dollar using coins?

There are several ways to make a dollar using coins with variable denominations. One way is to use 100 pennies, which are worth 1 cent each. Another way is to use 20 nickels, which are worth 5 cents each. You can also use 10 dimes, which are worth 10 cents each, or 4 quarters, which are worth 25 cents each.

2. What is the most efficient way to make a dollar using coins?

The most efficient way to make a dollar using coins is to use 4 quarters, which are worth 25 cents each. This method requires the least amount of coins and is the fastest way to make a dollar using coins with variable denominations.

3. Can I make a dollar using only one type of coin?

No, you cannot make a dollar using only one type of coin. In order to make a dollar, you will need a combination of coins with different denominations. For example, you can use 10 dimes, 20 nickels, or 100 pennies to make a dollar.

4. Is it possible to make a dollar using only bills?

Yes, it is possible to make a dollar using only bills. One way is to use a single one dollar bill. Another way is to use two half dollar bills, which are worth 50 cents each. You can also use a combination of smaller bills, such as two 50 cent bills, four 25 cent bills, or ten 10 cent bills.

5. What is the maximum number of coins I can use to make a dollar?

The maximum number of coins you can use to make a dollar is 100. This would require using 100 pennies, which are worth 1 cent each. You can also use a combination of other coins, such as 20 nickels, 10 dimes, or 4 quarters, to make a dollar using less coins.

Similar threads

  • General Math
Replies
28
Views
2K
Replies
16
Views
1K
Replies
5
Views
1K
Replies
4
Views
1K
  • General Math
Replies
3
Views
2K
Replies
15
Views
1K
Replies
3
Views
530
Replies
5
Views
247
  • General Math
Replies
6
Views
2K
Replies
9
Views
2K
Back
Top