View Single Post
awkward
awkward is offline
#9
Nov13-10, 01:32 PM
P: 325
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.