Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In how many ways can I have $1.50 using exactly 50 Coins? The coins may be pennies (1 cent), nickels (5 cents), dimes (10 cents) or quarters (25 cents).

share|improve this question
    
There is a solution of this problem, by a method quick and simple enough to do by hand, in the "Generating Functions" chapter of Concrete Mathematics by Graham, Knuth, and Patashnik. It is different from the three solutions below. –  MJD Oct 20 '12 at 12:21
2  
In how many ways can this problem be answered? –  Graphth Oct 20 '12 at 13:02
3  
Moreover, each and every way will elicit a scowl on the cashier's face when you try to use them to purchase a candy bar! –  Michael Joyce Oct 20 '12 at 14:08
    
As a comparison, if we differentiate arrangements of the coins, there are a lot more ways of arranging the change. Each choice of $x$, $x^5$, $x^{10}$, or $x^{25}$ when expanding the product $$ (x+x^5+x^{10}+x^{25})^{50}=\dots+277961174530259752\,x^{150}+\dots $$ corresponds to a particular choice of each of the $50$ coins. The coefficient given above yields the number that total to $\$1.50$. –  robjohn Oct 20 '12 at 14:26
add comment

7 Answers 7

Suppose that you use $p$ pennies, $n$ nickels, $d$ dimes, and $q$ quarters; then $p,n,d$, and $q$ must satisfy the system

$$\left\{\begin{align*} &p+n+d+q=50\\ &p+5n+10d+25q=150\;. \end{align*}\right.\tag{1}$$

Thus, you want to count the solutions to $(1)$ in non-negative integers.

The problem is small enough that you can easily solve by hand mostly using brute force. First, subtracting the first equation in $(1)$ from the second gives us the condition $$4n+9d+24q=100\;,\tag{2}$$

from which it’s clear that $q\le 4$.

Suppose that $q=4$; then $4n+9d=100-24\cdot4=4$, which clearly has only the solution $n=1,d=0$. At this point we’ve used four quarters, no dimes, and one nickel, for a total of $105$ cents from $5$ coins, and setting $p=45$ clearly gives the unique solution with $q=4$.

Now suppose that $q=3$, so that $(2)$ reduces to $4n+9d=28$. Clearly $d\le 3$. But both $4n$ and $28$ are divisible by $4$, while $9d$ is not for $0<d\le 3$, so we must have $d=0$ and $n=7$. We’ve now used $10$ coins that total $110$ cents, and it’s clear that setting $p=40$ gives us the unique solution with $q=3$.

Now suppose that $q=2$, so that $(2)$ reduces to $4n+9d=52$. Then $d\le 5$, and we can argue as in the previous case that $9d$ must be a multiple of $4$, so either $d=0$ and $n=13$, or $d=4$ and $n=4$. In the first case we have $15$ coins that total $115$ cents, and we must set $p=35$; in the second we have $10$ coins that total $110$ cents, and we must set $p=40$. These are clearly the only solutions when $q=2$.

If $q=1$, $(2)$ reduces to $4n+9d=76$, so that $d\le 8$. As in the previous two cases we must have $4\mid d$, so $d$ must be $0,4$, or $8$. These lead to the following solutions: $q=1,d=0,n=19,p=30$; $q=1,d=4,n=10,p=35$; and $q=1,d=8,n=1,p=40$.

Finally, if $q=0$, $(2)$ becomes $4n+9d=100$, the feasible values of $d$ are again $0,4$, and $8$, and the resulting solutions are: $q=0,d=0,n=25,p=25$; $q=0,d=4,n=16,p=30$; and $q=0,d=8,n=7,p=35$.

Thus, there are precisely $10$ solutions, and we’ve not just counted them, but also found them.

share|improve this answer
add comment

Let me try a generating function approach (first time trying, apologies if it is wrong):
$f_1=(1+nx+n^2x^2+\dots+n^{150}x^{150})$
$f_5=(1+nx^5+n^2x^{10}+\dots+n^{30}x^{150})$
$f_{10}=(1+nx^{10}+n^2x^{20}+\dots+n^{15}x^{150})$
$f_{25}=(1+nx^{25}+n^2x^{50}+\dots+n^6x^{150})$

The solution can be found within: $g=(f_1)(f_5)(f_{10})(f_{25})$.
More precisely, we need to locate the term $x^{150}n^{50}$, which signifies a sum of $150$ cents and $50$ coins.
Then, the coefficient represents the number of ways to do so.

An explanation of why it works:
For each $f_i$, it can be seen that exponent of $n$ represents the number of coins while exponent of $x$ represents the amount of money.
i.e. $n^5x^{125}$ means 5 coins for 125 cents.
When we multiply two terms, say $(n^ix^j)(n^kx^l)=n^{i+k}x^{j+l}$, it can be seen that the term conveniently computes the sum of money and also sum of coins used.

Calculation by hand is not recommended.
I tried it in Mathematica and I have the term $10n^{50}x^{150}$, which means that there should be 10 ways to do so.

Edit: In view of Soloveichik answer, this is how one might do it in Mathematica:
f=1/((1-n*x)(1-n*x^5)(1-n*x^10)(1-n*x^25));
series=SeriesCoefficient[f,{x,0,150},{n,0,50}]
Answer: 10

share|improve this answer
    
Well done! (+1) Do you see how your answer relates to i. m. soloveichik's answer? –  robjohn Oct 20 '12 at 15:44
    
In your edit, you probably intended $-$ instead of $+$ $$ f=\frac1{(1-nx)(1-nx^5)(1-nx^{10})(1-nx^{25})} $$ –  robjohn Oct 20 '12 at 15:52
    
Yes! I have only seen a simple variant of the generating function: $(1+x)(1+x^5+\dots)$ etc. Was wondering how to count multiplicity so I gave it a try. Seems like this is the normal approach. But I am embarrassed to say that I did not know it has to be $-$ though. Learned something today. Thanks for the correction. :) –  Yong Hao Ng Oct 20 '12 at 16:23
    
Indeed, $\frac1{1-x}=1+x+x^2+x^3+\dots$ whereas $\frac1{1+x}=1-x+x^2-x^3+\dots$ –  robjohn Oct 20 '12 at 16:27
    
Oh my, simple series expansion... I see it now. That was silly. =D –  Yong Hao Ng Oct 20 '12 at 17:07
add comment

The total number of ways of forming $1.50 using these coins can be calculated in GAP via:

NrRestrictedPartitions(150,[1,5,10,25]);

which returns 680.

With the additional restriction of there being exactly 50 coins, it can be found via:

NrRestrictedPartitions(150,[1,5,10,25],50);

The 10 possibilities are listed below as [ q, d, n, p ]:

[ 0, 0, 25, 25 ]
[ 0, 4, 16, 30 ]
[ 0, 8, 7, 35 ]
[ 1, 0, 19, 30 ]
[ 1, 4, 10, 35 ]
[ 1, 8, 1, 40 ]
[ 2, 0, 13, 35 ]
[ 2, 4, 4, 40 ]
[ 3, 0, 7, 40 ]
[ 4, 0, 1, 45 ]

The partitions themselves can be computed using: RestrictedPartitions(150,[1,5,10,25],50);

share|improve this answer
1  
Looking at the manual, NrRestrictedPartitions(150,[1,5,10,25],50); is a bit simpler. –  Chris Eagle Oct 20 '12 at 12:10
    
Updated, thanks again! –  Douglas S. Stones Oct 20 '12 at 21:38
add comment

Small examples of this sort of problem can be written out. In this case, start with the two equations:

$$p + 5n + 10d + 25q = 150$$ $$p+n+d+q = 50$$

Subtracting, we get:

$$4n + 9d + 24q = 100$$

Notice that since $9$ and $24$ are divisible by $3$ then $100-4n$ must be as well, so $n=3n'+1$ for some $n'$ and we get:

$$12n' + 4 + 9d + 24q = 100$$ or $$4n' + 3d + 8q = 32$$

Now we see that $d$ must be divisible by $4$, so we let $d=4d'$ and we have the equation:

$$n' + 3d' + 2q = 8$$

That is a much easier problem to solve by brute force.

Once you have a solution to this, you have solution to the original by taking:

$$(p,n,d,q) = (50-(3n'+1)-4d'-q, 3n'+1,4d',q)$$

So you need to find all nonegative solutions to: $$n'+3d'+2q = 8$$ with the added condition that $50-(3n'+1)-4d'-q\geq 0$. That last condition turns out to not affect the problem since it is true for all positive solutions.

share|improve this answer
add comment

You are looking for solutions of $$\tag1p+5n+10d+25q=150$$ $$\tag2p+n+d+q=50$$ in non-negative integers $p,n,d,q$.

Any amount $m$ combinable with nickels and dimes is nonnegative and divisible by 5 and uses between $\frac m{10}$ and $\frac m5$ coins. And on the other hand, for any nonnegative amount $m$ divisible by $5$ and $k$ with $5k\le m\le 10k$, there is a unique way to have $m$ cents in $k$ coins that are nickels and dimes. To see this, start with $\frac m5$ nickels and decrease the number of coins one by one (by replacing two nickels with a dime) untl you have the desired number of coins. One observes that this produces $\frac m5-k$ dimes and $2k-\frac m5$ nickels.

Thus we are looking for pairs $(p,q)$ with $p,q\ge0$, such that $150-p-25q$ is a nonnegative multiple of 5 and $5(50-p-q)\le 150-p-25q\le 10(50-p-q)$. The latter inequality is equivalent to $$\tag3 9p-15q\le 350$$ and $$\tag4 4p-20q\ge 100 .$$ Because $150-p-25q$ must be a multiple of $5$, $p$ must be a multiple of $5$. Hence write $p=5p'$. Then (3) and (4) become (after dividing out common factors) $$\tag5 q-3p'\ge -23$$ $$\tag6 p'-q\ge 5$$ And the nonnegativeness of $150-p-25q$ translates to $$\tag 7 -p'-5q\ge-30.$$ From $(5)+3\cdot(6)$, we conclude $-2q\ge -8$, i.e. $q\le 4$ With $q=0$, we obtain $5\le p'\le 7$ from (5) and (6). With $q=1$, we obtain $6\le p'\le 8 $. With $q=2$, we obtain $7\le p'\le 8 $. With $q=3$, we obtain $8\le p'\le 8 $. With $q=4$, we obtain $9\le p'\le 9 $. In all cases, (7) holds as well, thus we find a total of $3+3+2+1+1=10$ possible soluitons.

Explicitly, we have the following solutions for $(p,n,d,q)$:

$(25, 25, 0, 0)$, $(30, 16, 4, 0)$, $(35, 7, 8, 0)$, $(30, 19, 0, 1)$, $(35, 10, 4 ,1)$, $(40, 1, 8, 1)$, $(35, 13, 0 ,2)$, $(40, 4, 4, 2)$, $(40, 7, 0, 3)$, $(45, 1, 0, 4)$.

share|improve this answer
add comment

In Maple:

$f := \frac{1}{(1-tx)(1-tx^5)(1-tx^{10})(1-tx^{25})}:$

$T := taylor(f, x = 0, 151): $

$T150 := coeff(T, x, 150):$

$coeff(T150,t,50);$

Answer: 10

share|improve this answer
    
Correct, but a little explanation would be nice for those who don't know what you are doing. (+1) –  robjohn Oct 20 '12 at 15:50
add comment

I'm assuming that Douglas' GAP link is probably not easy to understand/implement so here's my explanation.

I'm not sure if there's a good way to solve these change-making problems by hand. The most common solution (that I know of) is algorithmic. Specifically, dynamic programming seems to be a "standard" solution. Since you have an extra constraint of precisely 50 coins you would need to do a bit extra for your DP. In particular, you'd first solve the general problem of the number of ways to form \$1.50 using those coins. Then you'd implement the DP so that you could produce the actual sets of coins that sum to \$1.50 (this is usually just a backtracking step after you finish filling in the memoization table). Finally you can filter those sets by size.

share|improve this answer
2  
So you're assuming the OP understands dynamic programming, and is able to write the code themself, but is unable to install a piece of software and type a command into it? –  Chris Eagle Oct 20 '12 at 12:09
    
I'm answering the question with a student's mindset. I would first see if I could solve it by hand. The next would be to solve it with an algorithm (well, programming it). I guess I have a hard time believing the OP literally just wanted to know that there were 10 ways to do this? –  roliu Oct 20 '12 at 12:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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