The coin change problem in the quantitative way

Question

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.

Answer 1

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.