# The coin change problem in the quantitative way

Today,I came across this problem:

Suppose you have a currency, named miso, in three denominations, $1, 10$ and $50$. In how many ways can $107$ miso be given in this currency if you have access to infinite number of coins of the said three denominations only?

$a)15 \quad \quad \quad b)16 \quad \quad \quad \quad c)17 \quad \quad \quad d)18 \quad \quad \quad \quad e)19$

I identified that this is the coin change problem and I am aware of the dynamic programming formulation for this, and till now my solution looks like this which is not at all intended by the problem setter, I am just wondering is it possible to solve this just by pencil-paper way? Of-course I don't want to do the dynamic programming steps in pencil paper.

-
If you can expand $\dfrac1{(1-x)(1-x^{10})(1-x^{50})}$ into series, and take the coefficient of $x^{107}$ ... –  Ｊ. Ｍ. Nov 19 '11 at 14:26
See this and this. –  Ｊ. Ｍ. Nov 19 '11 at 14:28
@J. M.:Are you really telling me to expand that series in an exam? –  Quixotic Nov 19 '11 at 14:43
That's why I gave you the link to Google Books. It shows how to do this cleverly, instead of differentiating 107 or so times... –  Ｊ. Ｍ. Nov 19 '11 at 14:45
add comment

## 1 Answer

The extra 7 miso have to be made up out of 1 coins, so let's ignore them.

Now ask how many 50 coins you use to make up 100 miso. Clearly you use 0, 1 or 2. Once you've decided that, then deciding how many 10 coins determines the number of 1 coins that you need. So we can easily enumerate all the possibilities by hand:

• Zero 50s, in which case the number of 10s is in {0,1,...,10} (there are 11 possibilities)
• One 50, in which case the number of 10s is in {0,1,...,5} (there are 6 possibilities)
• Two 50s, in which case the number of 10s is 0 (one possibility)

So there are 1 + 6 + 11 = 18 ways of making 107 miso out of 1s, 10s and 50s.

-
add comment