The Post Office down the road has run out of all stamps except 5c and 9c stamps. They have a large amount of each of these. What amounts of postage, up to $20 can the Post Office make with the stamps that they have left?
Solution
Experimenting will tell you that the Post Office can make up the following small amounts: 5c, 9c, 10c, 14c, 15c, 18c, 19c, 20c, 23c, 24c, 25c, 27c, 28c, 29c, 30c, 32c, 33c, 34c, 35c and 36c.
Once we know that they can make up 32c up to 36c we can see that they can do everything else up to $20. This is because they can keep adding 5c stamps like this:
| 32, | 32 + 5 = 37, | 32 + 5 + 5 = 42, | 42 + 5 = 47, | 47 + 5 = 52, ... |
| 33, | 33 + 5 = 38, | 33 + 5 + 5 = 43, | 43 + 5 = 48, | 48 + 5 = 53, ... |
| 34, | 34 + 5 = 39, | 34 + 5 + 5 = 44, | 44 + 5 = 49, | 49 + 5 = 54, ... |
| 35, | 35 + 5 = 40, | 35 + 5 + 5 = 45, | 45 + 5 = 50, | 50 + 5 = 55, ... |
| 36, | 36 + 5 = 41, | 36 + 5 + 5 = 46, | 46 + 5 = 51, | 51 + 5 = 56; ... |
Continually adding 5c stamps in this way will cover all the values from 32c up to 2000c = $20
Extension
What amounts of postage can they make with 5c and 12c stamps?