In how many ways can be expressed as a sum of four positive integers none of which is a multiple of ? Sums with different orders count as distinct.
Solution
Let the four integers be and write them as
Without any further constraint, there are possible combinations of values and for the . However, as , we must have
and given the range of the this implies or . The first of these has one case, the second has four:
| 1 | 1 | 1 | 1 | 4 |
| 1 | 2 | 2 | 2 | 7 |
| 2 | 1 | 2 | 2 | 7 |
| 2 | 2 | 1 | 2 | 7 |
| 2 | 2 | 2 | 1 | 7 |
Let , then and
The number of solutions to the original problem is equal to the number of solutions to plus four times the number of solutions to . By considering the numbers as a subset of we conclude that the number of solutions to is
Therefore, the number of solutions to the original problem is
= 674 562 = 254\,924\,324.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.