Making change
- Thread starter komark
- Start date
This is a little tricky. One way to find the number of ways to make change is to look at the coefficient of \(\displaystyle x^{175}\) in the expansion of
\(\displaystyle \frac{1}{(1-x^{5})(1-x^{10})(1-x^{25})}\).
This is tough to expand without technology. Even then it may make it grunt
.
\(\displaystyle \frac{1}{(1-x^{5})(1-x^{10})(1-x^{25})}\).
This is tough to expand without technology. Even then it may make it grunt
.
D
Deleted member 4993
Guest
komark said:
If I were to do this problem - I would use excel and write a small macro to physically count it out.
Once you specify the number of one coin, you only need to consider the possibilities of another.
You can have 0,1,...,17 dimes. (I chose dimes because nickles divides evenly into quarters)
In the case of 0 dimes, you can have 0,5,10,...,35 nickles, each of which specify a necessary amount of quarters (8 possibilities)
If you have one dime, you must have one of: 3,8,13,...,33 nickles (7 possibilities)
Two dimes => 1,6,11,...31 nickles (7 possibilities)
Three dimes => 4,9,14,19,24,29 (6 possibilities)
...
etc
It should get easier as the number of dimes go up, i.e.
14 dimes => 2 or 7 nickles (2 possibilities)
Just add these up
You can have 0,1,...,17 dimes. (I chose dimes because nickles divides evenly into quarters)
In the case of 0 dimes, you can have 0,5,10,...,35 nickles, each of which specify a necessary amount of quarters (8 possibilities)
If you have one dime, you must have one of: 3,8,13,...,33 nickles (7 possibilities)
Two dimes => 1,6,11,...31 nickles (7 possibilities)
Three dimes => 4,9,14,19,24,29 (6 possibilities)
...
etc
It should get easier as the number of dimes go up, i.e.
14 dimes => 2 or 7 nickles (2 possibilities)
Just add these up
I thought a little more for a "simple" solution, and here is what I came up with. Hopefully I did not make a mistake in my reasoning, but here it is:
If there are n quarters, the number of dimes possible is floor[(175-25n)/10] = floor[2.5(7-n)]. Given a number of dimes and quarters, it is easy to see that the number of nickles is already determined.
For example, if there are 5 quarters and 3 dimes, there must be 4 nickles. For this reason we may forget the nickles are even there.
So the answer is
\(\displaystyle \sum_{n=0}^7 \sum_{k=0}^{\lfloor 2.5(7-n) \rfloor} 1 = \sum_{n=0}^7 (\lfloor 2.5(7-n) \rfloor}+1) = 76\)
If there are n quarters, the number of dimes possible is floor[(175-25n)/10] = floor[2.5(7-n)]. Given a number of dimes and quarters, it is easy to see that the number of nickles is already determined.
For example, if there are 5 quarters and 3 dimes, there must be 4 nickles. For this reason we may forget the nickles are even there.
So the answer is
\(\displaystyle \sum_{n=0}^7 \sum_{k=0}^{\lfloor 2.5(7-n) \rfloor} 1 = \sum_{n=0}^7 (\lfloor 2.5(7-n) \rfloor}+1) = 76\)