I'm working on a little program and I stumbled across a small math problem I can't quite solve. This is what the program does.
A sum is generated. Now, the user can subtract either 3, 4, or 5 from this sum any number of times. The goal is to have the sum reduced to exactly 0. I want to know how many different ways that the sum can be reduced to zero, and ideally, what those number combinations are.
For example, if the Sum is 27, I could subtract 3 three times and 5 three times, or I could take 3 nine times, etc.
Furthermore, if we call a subtraction a "move", at some point the player will only have a certain number of moves, and I need to know how many ways I can drop 27 to 0 subtracting only 3, 4, or 5, using only, say, 6 moves.
I've mostly been getting around not knowing how to do this by guessing combinations of numbers, but I feel like there's an easier way.
Best Answer
If the order in which they are removed does matter, you can approach this via generating functions. The number of different ways in which you can do this without restriction on number of moves will be the coefficient of the $x^n$ term in the expansion of $(1+x^3+x^4+x^5)^N$ where $N\geq \lceil n/3\rceil$.
If you want to restrict the number of moves, you can put an upper bound on $N$ and move it lower to equal the number of moves. For example, if the number is $30$ and we want to have it done in at most 8 moves, look at the $x^n$ term in the expansion of $(1+x^3+x^4+x^5)^N$ where $N=8$. To make it exactly 8 moves, then remove the $+1$ term in the generating function.