I like the numbers 4 and 5. I like to add 4’s and 5’s together to make other numbers, such as 4 + 4 + 5 + 5 + 5 = 23. How many numbers from 1 to 1000 can be written as the sum of 4’s and 5’s?
Solution
994
A good way to solve this:
- Recognize that all multiples of 5 are possible.
- All numbers that are 1 less than a multiple of 5 are possible, by switching out one of the 5’s for a 4.
- For example, 30 = 5 + 5 + 5 + 5 + 5 + 5, so 29 = 4 + 5 + 5 + 5 + 5 + 5.
- By that logic, all numbers between multiples of 5 should be possible, by switching out up to four of the 5’s for 4’s.
- However, this does not work if there are not enough 5’s to switch out for 4’s – which is only true if there were fewer than four 5’s in the sum. So now we know all numbers 15 or greater can be written as the sum of 4’s and 5’s.
- If we just inspect the numbers from 1 to 14, we see that 6 of them cannot be written as the sum of 4’s and 5’s: 1, 2, 3, 6, 7, and 11. Hence 994 of the numbers from 1 to 1000 can be written as the sum of 4’s and 5’s.