0
$\begingroup$

How many different solutions does the following inequality have, in which $x_1$ and $x_2$ must be non-negative integers and $x_3$ must be a positive integer?

$x_1 + x_2 + x_3 \leq 13$

Struggling with this question. I know how to do it if all $x$'s are non-negative but the one positive $x$ is throwing me off.

$\endgroup$
2
$\begingroup$

Hint:

We can make a change of variables and use a throwaway variable to make things easier.

Let $y_1=x_1$, let $y_2=x_2$, let $y_3=x_3-1$ and let $y_4=13-x_1-x_2-x_3$.

What can you say about each of the values of $y_1,y_2,y_3,y_4$? What can you say about the sum $y_1+y_2+y_3+y_4$?

We have changed the problem now to the related problem of counting non-negative integer solutions to the system: $\begin{cases} y_1+y_2+y_3+y_4=12\\0\leq y_1\\0\leq y_2\\ 0\leq y_3\\ 0\leq y_4\end{cases}$ which should be in a known form.

$\endgroup$
  • $\begingroup$ The sum is 12. I assume the $x3 -1$ is to account for the fact we aren't including $x3 = 0$? $\endgroup$ – BlackBruceLee Oct 29 '17 at 22:01
  • $\begingroup$ @BlackBruceLee quite. It allows $y_3$ to equal zero despite $x_3$ not being able to equal zero. The sum is indeed twelve. The use of $y_4$ was to replace the $\leq$ sign in the original problem with a $=$ in the new problem (as that is the form that most people learn first and are more comfortable with). $\endgroup$ – JMoravitz Oct 29 '17 at 22:03
  • $\begingroup$ Do you recognize then what problem you can solve using the $y$'s instead of the $x$'s? Do you recognize that the number of solutions to this new problem is in fact the same number of solutions you have to your original problem? And finally, do you recognize how to solve the new problem? $\endgroup$ – JMoravitz Oct 29 '17 at 22:04
  • 1
    $\begingroup$ Is it $(12+4-1)C3$? So $15C3$ $\endgroup$ – BlackBruceLee Oct 29 '17 at 22:08
  • $\begingroup$ @BlackBruceLee Correct. Good job. $\endgroup$ – JMoravitz Oct 29 '17 at 22:08

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.