3
$\begingroup$

How many integer solutions of $x_1 + x_2 + x_3 + x_4 = 28$ are there with:

(a) $0 ≤ x_i ≤ 12$?

(b) $−10 ≤ x_i ≤ 20$?

(c) $0 ≤ x_i, x_1 ≤ 6, x_2 ≤ 10, x_3 ≤ 15, x_4 ≤ 21$?

\ \

My attempts (I was really only able to solve part (a) but I would appreciate if you could check my work for this one as well):

(a) First I took the total number of integer solutions with no restrictions: There would be ${28+3\choose 3}$ = ${31\choose 3}$ total solutions with no restrictions.

Then I used the inclusion exclusion principle and knew I would have to subtract [P(A) + P(B) + P(C) + P(D)] where A --> $x_1$ is greater than or equal to 13, ..., D--> $x_4$ is greater than or equal to 13. The probabilities of all these cases would equal ${15+3\choose 3}$ = ${18\choose 3}$ because once we assign 13 to one of the $x_i$ there would be $28 - 13 = 15$ remaining to distribute among the $x_i$ values. We would also need to choose which of the $x_i$ to give the 13 to so we would multiply the ${18\choose 3}$ by ${4\choose 1}$ = ${4\choose 1}{18\choose 3}$

We would then have to add back, since we "oversubtracted", the case in which there is an intersection between two of the $x_i$ or in other words two of the $x_i$ receive 13 or more. P$(A\bigcap B)$ = $28-2(13) = 2$ remaining to distribute among the $x_i$ values. So we would also have to choose which of the $x_i$ to give the 13 to so we would have ${4\choose 2}$ ways to choose them. So there would be ${4\choose 2}{2+3\choose 3}$ = ${4\choose 2}{5\choose 3}$ solutions in this case.

Thus the number of solutions would be: ${31\choose 3} - {4\choose 1}{18\choose 3} + {4\choose 2}{5\choose 3}$.

I'm not sure if this is correct and I'm really stuck on b and c so I would appreciate any help or feedback. Thank you!

$\endgroup$
  • 1
    $\begingroup$ Your answer for part (a) is completely correct. Nice job. $\endgroup$ – N. F. Taussig Oct 29 '18 at 19:08
  • $\begingroup$ Thank you @N.F.Taussig ! $\endgroup$ – Mathaholic24 Oct 29 '18 at 19:11
1
$\begingroup$

Your solution to the first question is completely correct.

How many integer solutions of the equation $x_1 + x_2 + x_3 + x_4 = 28$ are there with $-10 \leq x_i \leq 20$ for $1 \leq i \leq 4$?

Let $x_i' = x_i + 10$ for $1 \leq i \leq 4$. Since $-10 \leq x_i \leq 20$, $0 \leq x_i' \leq 30$. Substituting $x_i' - 10$ for $x_i$, $1 \leq i \leq 4$ and simplifying gives $$x_1' + x_2' + x_3' + x_4' = 68$$ which is an equation in the nonnegative integers, which we must solve subject to the restrictions that $x_i \leq 30$ for $1 \leq i \leq 4$. This is an Inclusion-Exclusion Principle problem analogous to the one you solved. Notice that at most two of the variables can simultaneously violate the restriction since $2 \cdot 31 = 62 < 68 < 93 = 3 \cdot 31$.

Applying the Inclusion-Exclusion Principle as above yields $$\binom{68 + 4 - 1}{4 - 1} - \binom{4}{1}\binom{37 + 4 - 1}{4 - 1} + \binom{4}{2}\binom{6 + 4 - 1}{4 - 1} = \binom{71}{3} - \binom{4}{1}\binom{40}{3} + \binom{4}{2}\binom{9}{3}$$

The last problem is a bit tedious. Let's see if we can save you some work.

How many nonnegative integer solutions of the equation $x_1 + x_2 + x_3 + x_4 = 28$ are there such that $x_1 \leq 6$, $x_2 \leq 10$, $x_3 \leq 15$, $x_4 \leq 21$?

Let $A$ be the event that $x_1 > 6$, $B$ be the event that $x_2 > 10$, $C$ be the event that $x_3 > 15$, and $D$ be the event that $x_4 > 21$. Without those restrictions, there are $$\binom{28 + 4 - 1}{4 - 1} = \binom{31}{3}$$ solutions, as you found. From these, we must subtract those solutions that violate one or more of the restrictions. To do so, we use the Inclusion-Exclusion Principle. The number of cases that violate one or more of the restrictions is $$|A \cup B \cup C \cup D| = |A| + |B| + |C| + |D| - |A \cap B| - |A \cap C| - |A \cap D| - |B \cap C| - |B \cap D| - |C \cap D| + |A \cap B \cap C| + |A \cap B \cap D| + |A \cap C \cap D| + |B \cap C \cap D| - |A \cap B \cap C \cap D|$$ It is possible to violate each of the restrictions. It is also possible to simultaneously violate the first and second restrictions, first and third restrictions, and second and third restrictions. However, it is not possible to simultaneously violate the first and fourth restrictions, second and fourth restrictions, or third and fourth restrictions, nor it is possible to simultaneously violate any three or four of the restrictions simultaneously. Hence, $$|A \cap B \cap C \cap D| = |A| + |B| + |C| + |D| - |A \cap B| - |A \cap C| - |B \cap C|$$ as all the remaining terms are equal to zero. Can you proceed?

$\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.