How many unique ways are there to make change for a dollar?
This is a much harder problem than it initially seems. Credit goes to Kimota94 for attempting it - he had the right idea but used multiplication between the steps instead of addition which resulted in a much larger answer. Nobody else seemed brave enough to venture an answer.
I used a recursive approach to come up with the answer.
Let An be the number of ways to make n cents with pennies.
Let Bn be the number of ways to make n cents with pennies and nickels.
Let Cn be the number of ways to make n cents with pennies, nickels, and dimes.
Let Dn be the number of ways to make n cents with pennies, nickels, dimes, and quarters.
The question is asking us to find D100
The number of ways to make Dn when n >= 25 if at least 1 quarter is used is Dn-25, while the number of ways to make Dn when no quarter is used is Cn.
Therefore: Dn = Cn + Dn-25, n >= 25
Cn = Bn + Cn-10, n>=10
Bn = An + Bn-5, n>=5
It is obvious that An is always 1.
It is slightly less obvious, but fairly clear to see that Bn is 1+x where x is n/5 truncated to the integer portion of the quotient. We can show this obvious solution by proving it true for the first few values of n and then relying on the recursive definition above.
If n <>n = 1 (only pennies are possible). For n = 5, there are two choices: 1 nickel or 5 pennies. If 5 < n <>
Therefore B5 = 2, B10 = 3, B15 = 4, ..., B100=21.
We want D100, let's use some substitution here:
D100 = C100+D75
D100 = C100+C75+D50
D100 = C100+C75+C50+D25
D100 = C100+C75+C50+C25+1
C100 = B100+B90+B80+B70+B60+B50+B40+B30+B20+B10+1
C75 = B75+B65+B55+B45+B35+B25+B15+B5 (note no +1, since C5 = B5)
C50 = B50+B40+B30+B20+B10+1
C25 = B25+B15+B5
Substituting with the values of Bn in the formula above we see:
C100 = 21+19+17+15+13+11+9+7+5+3+1 = 121
C75 = 16+14+12+10+8+6+4+2 = 72
C50 = 11+9+7+5+3+1 = 36
C25 = 6+4+2 = 12
D100 = C100+C75+C50+C25+1 = 121+72+36+12+1 = 242
So there are 242 ways to uniquely make change for $1 using pennies, nickels, dimes, and quarters.