1. The problem statement, all variables and given/known data What is the smallest number of coins needed to pay in exact change an change less then a dollar (coins are 1, 5, 10, 25 and 50 cents)? 2. Relevant equations No relevant equations apart from a theorem: Numbers between n and k inclusive, k>n, if k - n + 1 3. The attempt at a solution I tried a variety of solutions such as going backwards. I looked that to make up to 4 cents, we needed 4 1cent coins. Then, for 9 cents we need either 1 5cent coin and 4 1cent or 9 1cent, and obviously it should be the former option. I tried going this way and messed up, so if anyone can clarify if this is the correct method or there is some other way. Thanks Other info: This is from a combinatorics textbook, by Niven. However, at this point, apart from the theorem above, we are assumed not to have learnt any theory (i.e. permutations, combinations etc). Thanks.