math question?

Question

here's an equation

a(25)+b(10)+c(5)+d(1)
=1000

can anyone tell me how to figure out all the combinations of a,b,c and d so that the equation adds up to 1000. doesnt have to all, coz they over 140 000. but just the formula to figure it out. thanx. the actual question is given a $10.00 note, using just coins (cent, dime, nickel and quarters), how many ways can i given back $10.00 in change. not just the number of ways, but also the ways themselves. just an idea is enuf. thanx again

Answer 1

First choose number of quarters,
then choose number of dimes,
then choose number of nickels.
Pennies make up the rest.

However, let's calculate it the other way around to make it easier.

Pennies:
Let say we have after choosing quarters, dimes and nickels, we have Z cents remaining.
There is only 1 way to make this up using pennies, Z pennies.
1 way.
Eg. 1000 pennies.

Nickles:
After choosing quarters and dimes, we have Y cents remaining. We can have as low as 0 nickels, and as much as Y/5 nickels.
Y/5 + 1 ways.
Eg. 1000/5 = 200.
0 nickels to 200 nickels. 201 ways.

Dimes:
Let X be the number of cents after choosing quarters. Unfortunately, dimes don't go into quarters evenly, so we have 2 scenarios: one where we have an even number of quarters (00, 50 cents), one with odd. (25, 75 cents)

Lets do EVEN first:
As many as 0 dimes, and at most X/10.
Now if we have 0 dimes, Then Y = X.
If we X/10 dimes, Y = 0.
Y = X - b(10)
There are Y/5 + 1 ways to make change for the remaining amount

So lets sum it up
SUM [b = 0 to X/10] (Y/5 + 1)
= SUM [b = 0 to X/10] ((X - b*10)/5 + 1)
= SUM [b = 0 to X/10] 1 + X/5 - 2*b

= SUM [b = 0 to X/10] (1 + X/5)
- SUM [b = 0 to X/10] 2*b

Notes: Sum of 1 + 2 + 3 + ... + n = n(n+1)/2
Sum of 1^2 + 2^2 + 3^2 + ... + n^2 = n*(n+1)*(2n+1)/6

= (X/10 + 1)(1 + X/5)
- 2* (X/10)(X/10 + 1)/2
= (X/10 + 1)(1 + X/5)- (X/10)(X/10 + 1)
= (X/10 + 1)(1 + X/5 - X/10)
= (X/10 + 1)(1 + X/10)
= (1 + X/10)^2


ODD:
This is pretty much the same except, lets set aside 5 cents from the beginning. This 5 cents can be made either by nickels or pennies.
This gives us
= ((X-5)/10 + 1)^2 + (X-5)/10 + 1)
= ((X-5)/10 + 1)((X-5)/10) + 2)

Quarters:
X is cents remaining after choosing quarters.
X = 1000 - a(25)
X/10 = 100 - 2.5 * a

EVEN:
We can have 0 quarters to 40 quarters.
SUM [a = 0 to 40, and a is even] (1 + X/10)^2
Sub in for X. Technically we should sub in a variable for a/2, but I'm feeling lazy.
SUM [(a/2) = 0 to 20] (100 - 2.5 * a + 1)^2
SUM [(a/2) = 0 to 20] (101 - 2.5 * a )^2 Multiply out
SUM [(a/2) = 0 to 20] 10201 - 505 a + 6.25 a^2

= SUM [(a/2) = 0 to 20] 10201
- SUM [(a/2) = 0 to 20] 1010 (a/2)
+ SUM [(a/2) = 0 to 20] 25 (a/2)^2

= 10201 * 21 - 1010 (20)(21)/2 + 25 (20)(21)(41)/6
= 214221 - 212100 + 71750
= 73871

ODD:
X = 1000 - 25a
X - 5 = 995 - 25a
(X-5)/10 = 99.5 - 2.5 a
Let a = 2t - 1, t = (a+1)/2
(X-5)/10 = 99.5 - 2.5(2t-1)
(X-5)/10 = 99.5 - 5t +2.5
(X-5)/10 = 102 - 5t

SUM [a = 1 to 39, and a is odd] ((X-5)/10 + 1)((X-5)/10) + 2)
= SUM [t = 1 to 20](102 - 5t + 1) (102 - 5t + 2)
= SUM[t = 1 to 20](103 - 5t) (104 - 5t)
= SUM[t = 1 to 20]10712 - 1035 t + 25t^2

= 10712 * 20 - 1035(20)(21)/2 + 25(20)(21)(41)/6
= 214240 - 217350 + 71750
= 68640

TOTAL
68640 + 73871 = 142511

Answer 2

if you just want to find the combinations themselves you can do it with simple computer program:
for every a = 0..1000/25
for every b = 0..1000/10
for every c = 0..1000/5
if the sum of them is not more than 1000 there is a d that solves this equation.