How many total ways are there to make one dollar ?

- ganeshie8

How many total ways are there to make one dollar ?

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- schrodinger

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- ganeshie8

|dw:1449945419248:dw|

- ganeshie8

using above denominations...

- anonymous

29 in coins but with a dollar bill 30

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- ganeshie8

100 is a very good guess, but it isn't correct...

- anonymous

wait it is 293

- ganeshie8

293 is correct !

- Christos

how did you find ?

- ganeshie8

Could you also show how you arrived at that :)

- anonymous

you have to figure out how many half dollar coins you need how many pennies you need and how many nickels you need

- anonymous

but the cheating way is looking it up

- ParthKohli

oh I know this\[1x_1+5x_2+10x_3+25x_4+50x_5+100x_6=100\]nonnegative integral solutions of this

- anonymous

what the frik are those

- malcolmmcswain

http://prntscr.com/9ddfxx

- malcolmmcswain

:/

- ParthKohli

now what we do is apply a trick to convert this to an algebra problem\[(1+x+x^2+\cdots)(1+x^5+x^ {10}+\cdots)(1+x^{10}+{x}^{20}+\cdots)\cdots\]consider this expression. we can find the coefficient of \(x^{100}\) and that is our answer.

- Christos

I would image solving this with recursion in programming . Wouldn't you otherwise had to build a huge tree of every combination by hand

- ganeshie8

generating functions make the life easy but it seems finding the coefficient isn't easy here...

- ParthKohli

wait do we only have the coins given in the picture?

- ParthKohli

am I allowed to use a cent hundred times? because that picture only shows two of them

- ganeshie8

Ofcourse coins can be used any number of times

- ParthKohli

thanks.\[\frac{1}{1-x}\cdot\frac{1}{1-x^5}\cdot \frac{1}{1-x^{10}}\cdots \frac{1}{1-x^{100}}\]

- ParthKohli

lol yeah, finding the coefficient is tough but not impossible

- ganeshie8

http://www.wolframalpha.com/input/?i=maclaurin+series+of+1%2F%28%281-x%29%281-x%5E5%29%281-x%5E10%29%281-x%5E25%29%281-x%5E50%29%281-x%5E100%29%29

- ganeshie8

keep clicking "More terms..."

- ParthKohli

nice pattern.
1, 2, 4, 6, 9, 13, 18, 24, 31, 39, 50...

- Christos

int make_change(int amount, int[] denominations) {
int[] change = new int[amount+1];
change[0] = 1;
for (int i = 1; i <= amount; i++) {
for (int denomination : denominations) {
if (i >= denomination) {
change[i] += change[i-denomination];
}
}
}
return change[denomination];
}

- ParthKohli

well at least we could convert this problem to a form which Wolfram|Alpha accepts haha

- ganeshie8

Nice :)

- ParthKohli

what is your solution?

- ganeshie8

Page11
example 3.5
http://db.math.ust.hk/notes_download/elementary/algebra/ae_A11.pdf

- ganeshie8

that solution is a bit complicated..

- ParthKohli

oh haha but he did use generating functions

- ikram002p

nice! i like those generating function problems. i have worked on generating integrals like Voltera equations very interesting ways to solve :O

- danica518

start with 1 cent splits

- danica518

|dw:1449953244057:dw|

- danica518

|dw:1449953553432:dw|

- danica518

how about building up the restrictictions like so, the way to use the lower numbers is they will always sum to a coin of a higher value

- danica518

for example if a 5 is used, there there have to k number of sets of 1s that are a multiple of 5, if 1 cent is used

- ganeshie8

yeah the coefficients in generating function are also changing in multiples of 5
http://www.wolframalpha.com/input/?i=maclaurin+series+of+1%2F%28%281-x%29%281-x%5E5%29%281-x%5E10%29%281-x%5E25%29%281-x%5E50%29%281-x%5E100%29%29

Looking for something else?

Not the answer you are looking for? Search for more explanations.