1
$\begingroup$

How many nonnegative integer solutions are there to the equation $x_1+x_2+x_3+x_4 = 18$ with $$−2\leq x_3 \leq 4\\0 \leq x_2 \leq 5\\3 \leq x_1 \leq8\\ −3 \leq x_4 \leq 13$$

when its in is simple form its easy to solve that but here in this kind of question how i solve it ?

$\endgroup$
  • 2
    $\begingroup$ If you say "non-negative," isn't $-2\leq x_3\leq 4$ a bit redundant - can't you set $x_3\leq 4$? $\endgroup$ – Thomas Andrews Oct 17 '17 at 21:19
  • $\begingroup$ nice so i can say all like that ? x1≤5 and x4≤16 ? $\endgroup$ – NedyLearing Oct 17 '17 at 21:22
  • $\begingroup$ If the question really says "non-negative," then yes. $\endgroup$ – Thomas Andrews Oct 17 '17 at 21:25
  • $\begingroup$ Could you provide the exact wording of the question? The question would make more sense if it said "How many integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 18$ with $ 3 \leq x_1 \leq 8$, $0 \leq x_2 \leq 5$, $-2 \leq x_3 \leq 4$, and $-3 \leq x_4 \leq 13$. $\endgroup$ – N. F. Taussig Oct 17 '17 at 22:48
  • 2
    $\begingroup$ May I suggest removing "nonnegative"? $\endgroup$ – rtybase Oct 18 '17 at 10:56
0
$\begingroup$

I never miss a chance to recommend a good book. "How to Count" covers the relevant material and even more and it's a good book indeed.

Now to the problem. Assuming mistranslating "nonnegative" has a higher likelihood than copy and pasting math expressions, twice (one for "$-2 \leq ...$" and one for "$-3 \leq ...$") I will stick to the following version:

How many integer solutions are there to the equation ...

This class of problems is solved with what is called generating functions. First of all $$−2\leq x_3 \leq 4 \Leftrightarrow 0 \leq x_3+2 \leq 6$$ $$−3\leq x_4 \leq 13 \Leftrightarrow 0 \leq x_4+3 \leq 16$$ So, with a substitution like $y_1=x_1, y_2=x_2, y_3=x_3+2, y_4=x_4+3$ the problem is equivalent to $$y_1+y_2+y_3+y_4=23$$ $$3\leq y_1 \leq 8$$ $$0\leq y_2 \leq 5$$ $$0\leq y_3 \leq 6$$ $$0\leq y_4 \leq 16$$

The generating function for this problem is $$(y^3+y^4+...+y^8)(y^0+y^1+...+y^5)(y^0+y^1+...+y^6)(y^0+y^1+...+y^{16})$$ the coefficient near the $y^{23}$ term is the answer, which is $232$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.