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.

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.

share|improve this question
1  
If you can expand $\dfrac1{(1-x)(1-x^{10})(1-x^{50})}$ into series, and take the coefficient of $x^{107}$ ... –  J. M. Nov 19 '11 at 14:26
1  
See this and this. –  J. M. 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... –  J. M. Nov 19 '11 at 14:45
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
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.