Question

How many total ways are there to make one dollar ?

Answer 1

using above denominations...

Answer 2

29 in coins but with a dollar bill 30

Answer 3

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

Answer 4

wait it is 293

Answer 5

293 is correct !

Answer 6

how did you find ?

Answer 7

Could you also show how you arrived at that :)

Answer 8

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

Answer 9

but the cheating way is looking it up

Answer 10

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

Answer 11

what the frik are those

Answer 12

http://prntscr.com/9ddfxx

Answer 13

:/

Answer 14

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.

Answer 15

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

Answer 16

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

Answer 17

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

Answer 18

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

Answer 19

Ofcourse coins can be used any number of times

Answer 20

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

Answer 21

lol yeah, finding the coefficient is tough but not impossible

Answer 22

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

Answer 23

keep clicking "More terms..."

Answer 24

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

Answer 25

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];
}

Answer 26

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

Answer 27

Nice :)

Answer 28

what is your solution?

Answer 29

Page11
example 3.5

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

Answer 30

that solution is a bit complicated..

Answer 31

oh haha but he did use generating functions

Answer 32

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

Answer 33

start with 1 cent splits