1
$\begingroup$

Determine the number of integer solutions for $x_1+x_2+x_3+x_4+x_5 < 40$

a) $x_i \geq 0, i = 1,2,\dots,5$.

b) $x_i \geq -3, i = 1,2,\dots,5$.

c) $-3 \leq x_i \leq 10, i = 1,2,\dots,5$.

My try is

a)$x_1+x_2+x_3+x_4+x_5+x_6=40$

${40+6-1 \choose 40}=1221759$

need help on b) an c)

$\endgroup$
  • $\begingroup$ For b, let $y_i=x_i+3$, and so $x_i=y_i-3$, so $\sum_i (y_i-3)=40$, so $\sum_i y_i= 40+18$ where $y_i \geq 0$ and now you've reduced the problem to the type of part a. $\endgroup$ – usr0192 Nov 25 '15 at 23:53
  • $\begingroup$ Be careful. In part (a), since $x_1, x_2, x_3, x_4, x_5$ are non-negative integers whose sum is less than $40$, $x_6 \geq 1$. Let $y_6 = x_6 - 1$. Then $y_6$ is a non-negative integer. If we substitute $y_6 + 1$ for $x_6$ in the equation $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 40$$ we obtain $$x_1 + x_2 + x_3 + x_4 + x_5 + y_6 = 39$$ which is an equation in the non-negative integers with $\binom{39 + 5}{5} = \binom{44}{5}$ solutions in the non-negative integers. $\endgroup$ – N. F. Taussig Nov 27 '15 at 1:32
1
$\begingroup$

For the first problem, observe that if $x_1, x_2, x_3, x_4, x_5$ are non-negative integers satisfying the inequality $$x_1 + x_2 + x_3 + x_4 + x_5 < 40 \tag{1}$$ then $x_1 + x_2 + x_3 + x_4 + x_5 \leq 39$. Let $x_6 = 39 - (x_1 + x_2 + x_3 + x_4 + x_5)$. Then $x_6$ is a non-negative integer. Moreover, the number of solutions of inequality 1 in the non-negative integers is equal to the number of solutions to the equation $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 39 \tag{2}$$ in the non-negative integers. A particular solution to equation 2 corresponds to a choice of where to insert five addition signs in a row of $39$ ones. Hence, the number of solutions of equation 2 in the non-negative integers is $$\binom{39 + 5}{5} = \binom{44}{5}$$ since we must select which five of the $44$ symbols ($39$ ones and five addition signs) are addition signs.

For the second problem, let $y_k = x_k + 3$ for $1 \leq k \leq 5$. Since each $x_k \geq -3$, each $y_k$ is a non-negative integer. Substituting $y_k - 3$ for $x_k$, $1 \leq k \leq 5$ in inequality 1 yields \begin{align*} y_1 - 3 + y_2 - 3 + y_3 - 3 + y_4 - 3 + y_5 - 3 & < 40\\ y_1 + y_2 + y_3 + y_5 + y_5 & < 55 \tag{3} \end{align*} Then $y_1 + y_2 + y_3 + y_4 + y_5 \leq 54$. Let $y_6 = 54 - (y_1 + y_2 + y_3 + y_4 + y_5)$. Then $y_6$ is a non-negative integer. The number of solutions of inequality 3 in the non-negative integers is equal to the number of solutions of the equation $$y_1 + y_2 + y_3 + y_4 + y_5 + y_6 = 54 \tag{4}$$ in the non-negative integers. The number of solutions of equation 4 in the non-negative integers is

$$\binom{54 + 5}{5} = \binom{59}{5}$$

For the third problem, we must exclude those solutions of the second problem in which at least one of the variables $x_1, x_2, x_3, x_4, x_5$ exceeds $10$. Since $y_k = x_k + 3$ for $1 \leq k \leq 5$, this is equivalent to excluding those solutions of equation 4 in which one or more of the variables $y_1, y_2, y_3, y_4, y_5$ exceeds $13$. Since $4 \cdot 14 = 56 > 54$, at most three of the variables $y_1, y_2, y_3, y_4, y_5$ can exceed $13$ simultaneously.

Suppose $y_1 > 13$. Then $z_1 = y_1 - 14$ is a non-negative integer. Substituting $z_1 + 14$ for $y_1$ in equation 4 yields $$z_1 + y_2 + y_3 + y_4 + y_5 + y_6 = 40 \tag{5}$$ Equation 5 has

$$\binom{40 + 5}{5} = \binom{45}{5}$$

solutions in the non-negative integers. Since there are $\binom{5}{1}$ ways for one of the variables $y_1, y_2, y_3, y_4, y_5$ to exceed $13$, the number of solutions of equation 4 in the non-negative integers in which one of the variables $y_1, y_2, y_3, y_4, y_5$ exceeds $13$ is

$$\binom{5}{1}\binom{45}{5}$$

Suppose $y_1, y_2 > 13$. Let $z_1 = y_1 - 14$; let $y_2 = z_2 - 14$. Then $z_1, z_2$ are non-negative integers. Substituting $z_1 + 14$ for $y_1$ and $z_2 + 14$ for $y_2$ in equation 4 yields

$$z_1 + z_2 + y_3 + y_4 + y_5 + y_6 = 26 \tag{6}$$

Equation 6 is an equation with

$$\binom{26 + 5}{5} = \binom{31}{5}$$

solutions in the non-negative integers. Since there are $\binom{5}{2}$ ways for two of the variables $y_1, y_2, y_3, y_4, y_5$ to exceed $13$, the number of solutions of equation 4 in the non-negative integers in which two of the variables $y_1, y_2, y_3, y_4, y_5$ exceed $13$ is

$$\binom{5}{2}\binom{31}{5}$$

By similar argument, the number of solutions of equation 4 in the non-negative integers in which three of the variables $y_1, y_2, y_3, y_4, y_5$ exceed $13$ is

$$\binom{5}{3}\binom{12 + 5}{5} = \binom{5}{3}\binom{17}{5}$$

By the Inclusion-Exclusion Principle, the number of solutions of the second problem in which $x_k \leq 10$ for $1 \leq k \leq 5$, is

$$\binom{59}{5} - \binom{5}{1}\binom{45}{5} + \binom{5}{2}\binom{31}{5} - \binom{5}{3}\binom{17}{5}$$

$\endgroup$
  • $\begingroup$ What happened to the displays? $\endgroup$ – Mike Jones Feb 7 '16 at 13:21
  • $\begingroup$ @MikeJones When I scroll over the displays, the hidden expressions or equations are revealed. What happens when you scroll over them? I hid the expressions or equations since I wanted the person who posted the question to think about the answers rather than passively reading them. $\endgroup$ – N. F. Taussig Feb 7 '16 at 15:39
  • $\begingroup$ Cool! I simply didn't know about that feature / technique. $\endgroup$ – Mike Jones Feb 9 '16 at 15:09

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.