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.
IRL ABooklet
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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.