Edmund's Brainteasers
Problem 6
Solution
Problem 6: The treasurer's stamps. Solution
The treasurer cannot make up 63 pence from 5 pence and 17 pence only but can make up any higher value. To show that every higher value can be made up we need to show we can make up 64, 65, 66, 67 and 68 pence. Then we can get any bigger value adding a multiple of 5 to one of these, for example 69 = 64 + 5 etc. But 64 = 6 x 5 + 2 x 17, 65 = 13 x 5, 66 = 3 x 5 + 3 x 17, 67 = 10 x 5 + 1 x 17, 68 = 4 x 17.
It remains to show the treasurer can't make up 63 pence. Clearly 63 is not divisible by 5, nor is 63-17 = 46, nor 63 - 2 x 17 = 29, nor 63 - 3 x 17 = 12.