2
$\begingroup$

I feel like that I should use generating functions but even if I can count the combinations, I can't find a way to get the ones with an odd number of coins. Hints?

P. S. Cents, nickels, dimes and quarters are allowed

1 dollar = 100 cents
1 nickel = 5 cents
1 dime = 10 cents
1 quarter = 25 cents

$\endgroup$
  • $\begingroup$ What coins are allowed? What did you try? $\endgroup$ – Qudit Sep 20 '17 at 20:06
  • $\begingroup$ It might be worth finding all the ways to make change (which is even + odd), then finding (even-odd) by slightly changing the generating function. From that you can solve for even and odd. $\endgroup$ – Steve D Sep 20 '17 at 20:09
  • $\begingroup$ maybe you should explain what nickels, etc. are !? $\endgroup$ – G Cab Sep 20 '17 at 20:25
  • $\begingroup$ @SteveD I don't get this bit. With the generating functions I can determine the number of combinations by finding the 100 exponent but I have no clue about how to proceed. :( $\endgroup$ – AMeoni Sep 20 '17 at 20:57
2
$\begingroup$

Here's the generating function solution:

The generating function that counts all ways of making change is:

$$ \text{all}(x) = \frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})} $$

[That is, the coefficient of $x^{100}$ is the number of ways to make change of a dollar.]

If we look at the function

$$ \text{alternating}(x) = \frac{1}{(1+x)(1+x^5)(1+x^{10})(1+x^{25})} $$

Then the coefficient of $x^{100}$ is (number of ways to do it with even number of coins) - (number of ways to do it with odd number of coins) [can you see why?]. From here you can easily solve for both (even number of ways) and (odd number of ways).

$\endgroup$
  • $\begingroup$ From Steve D I realise that Marcus M wanted to help me understand the logic behind it, I get that I don't really need to know how many coins I am using, all I need to know is that the total number of the solution is odd+even (obviously), hence as both Marcus M and Steve D suggest, it seems that $$ odd(x)= \frac{all(x)−alternating(x)}{2}$$ $\endgroup$ – AMeoni Sep 21 '17 at 22:51
2
$\begingroup$

Here's a hint for a generating function solution: let $a_{m,n}$ be the number of ways to make change for $n$ cents with $m$ coins.

Find the generating function $$F(x,y) = \sum_{m,n} a_{m,n} y^m x^n.$$

Try to manipulate this generating function to get the generating function for the number of ways to make change with an odd number of coins. Hover below for the solution:

Notice that $$\frac{F(x,y) - F(x,-y)}{2} = \sum_{m,n} a_{2m +1,n} y^{2m+1}x^n.$$ This would imply $\frac{F(x,1) - F(x,-1)}{2}$ is the generating function for the number of ways to make change with an odd number of coins.

$\endgroup$
0
$\begingroup$

Hint: Since $100$ is an even number, we must use an even number of odd summands. Therefore, to use an odd number of coins, we must use an odd number of dimes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.