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$
4
  • $\begingroup$ What coins are allowed? What did you try? $\endgroup$
    – Qudit
    Commented Sep 20, 2017 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
    Commented Sep 20, 2017 at 20:09
  • $\begingroup$ maybe you should explain what nickels, etc. are !? $\endgroup$
    – G Cab
    Commented Sep 20, 2017 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
    Commented Sep 20, 2017 at 20:57

3 Answers 3

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$
1
  • $\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
    Commented Sep 21, 2017 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .