4
$\begingroup$

How many nonnegative integer solutions are there to $$x_1 + x_2 + \ldots + x_5 = 20$$

(a) With $x_i \leq 10$?

(b) With $x_i \leq 8$?

(c) With $x_1 = 2x_2$?

Here is what I did:

(a) ${24\choose 4} - 5{14\choose 4}$

I did this by assigning $10$ to an $x_i$ and then going from there. I subtracted this case from the total number of cases to get the number of desired cases.

I'm thinking this should rather be ${24\choose 4} - 5{13\choose 4}$ but I am not sure...I think this because maybe I should have assigned $11$ to an $x_i$ rather than $10$ and then subtracted this from the total number of ways.

(b) $5{15\choose 3} - 4{6\choose 3}$

I'm also confused with my own work for this one. I originally assigned $8$ to an $x_i$ and got rid of this variable from consideration. Then I had $12$ remaining for $n$ and $3$ for $m$ so I had ${15\choose 3}$ outcomes. Then I subtracted the case in which another variable received $9$ or more so I assigned $9$ to another variable. And then I had $3$ remaining for $n$ and $3$ for $m$, so I had ${6\choose 3}$. Since there were $4$ candidates for the greater than $8$ votes I used ${4\choose 1}$.

(c) I really need help with this part, I'm not even sure where to start...

$\endgroup$
  • 1
    $\begingroup$ This is a great question! I'm stumped as well! $\endgroup$ – Parley Oct 10 '18 at 1:40
1
$\begingroup$

How many nonnegative integer solutions are there to the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 20$$ if $x_i \leq 10$ for $1 \leq i \leq 5$?

Without restrictions, the number of solutions of the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 20 \tag{1}$$ is $$\binom{20 + 5 - 1}{5 - 1} = \binom{24}{4}$$ as you found. The condition is violated if one of the five variables exceeds $10$. Note that at most one of the variables can exceed $10$ since $2 \cdot 11 = 22 > 20$.

Choose which of the five variables violates the condition. Since the equation is symmetric with respect to the variables, we may suppose it is $x_1$. Let $x_1' = x_1 - 11$. Then $x_1'$ is a nonnegative integer. Substituting $x_1' + 11$ for $x_1$ in equation 1 and simplifying yields $$x_1' + x_2 + x_3 + x_4 + x_5 = 9 \tag{2}$$ Equation 2 is an equation in the nonnegative integers with $$\binom{9 + 5 - 1}{5 - 1} = \binom{13}{4}$$ Hence, there are $$\binom{5}{1}\binom{13}{4}$$ solutions that violate the restrictions.

Hence, there are $$\binom{24}{4} - \binom{5}{1}\binom{13}{4}$$ admissible solutions, so your second attempt was right.

How many nonnegative integer solutions are there to the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 20$$ if $x_i \leq 8$ for $1 \leq i \leq 5$?

In this case, at most two of the variables could exceed the restrictions since $2 \cdot 9 = 18 < 20 < 27 = 3 \cdot 9$.

Choose which of the five variables exceeds the restriction. Since the equation is symmetric with respect to the variables, we may suppose it is $x_1$. Let $x_1' = x_1 - 9$. Then $x_1'$ is a nonnegative integer. Substituting $x_1' + 9$ for $x_1$ in equation 1 and simplifying yields $$x_1' + x_2 + x_3 + x_4 + x_5 = 11 \tag{3}$$ Equation 3 is an equation in the nonnegative integers with $$\binom{11 + 5 - 1}{5 - 1} = \binom{15}{4}$$ solutions. Hence, there are $$\binom{5}{1}\binom{15}{4}$$ cases in which one of the variables violates a restriction.

However, if we subtract this from the total, we will have subtracted too much since we have counted each case in which two of the variables violate a restriction twice, once for each way we could have designated one of the variables as the one that violates a restriction. Therefore, we need to add these cases back.

There are $\binom{5}{2}$ ways to select which two of the five variables violates a restriction. Since the equation is symmetric with respect to the variables, we may suppose they are $x_1$ and $x_2$. Let $x_1' = x_1 - 9$ and $x_2' = x_2 - 9$. Substituting $x_1' + 9$ for $x_1$ and $x_2' + 9$ for $x_2$ in equation 1 and simplifying yields $$x_1 + x_2 + x_3 + x_4 + x_5 = 2 \tag{4}$$ Equation 4 is an equation in the nonnegative integers with $$\binom{2 + 5 - 1}{5 - 1} = \binom{6}{4}$$ solutions. Thus, there are $$\binom{5}{2}\binom{6}{4}$$ cases in which two of the restrictions are violated.

By the Inclusion-Exclusion Principle, the number of admissible solutions is $$\binom{24}{4} - \binom{5}{1}\binom{15}{4} + \binom{5}{2}\binom{6}{4}$$

How many nonnegative integer solutions are there to the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 20$$ if $x_i \leq 8$ if $x_1 = 2x_2$?

Consider cases.

  1. If $x_1 = x_2 = 0$, then $x_3 + x_4 + x_5 = 20$.
  2. If $x_1 = 2$ and $x_2 = 1$, then $x_3 + x_4 + x_5 = 17$.
  3. If $x_1 = 4$ and $x_2 = 2$, then $x_3 + x_4 + x_5 = 14$.
  4. If $x_1 = 6$ and $x_2 = 3$, then $x_3 + x_4 + x_5 = 11$.
  5. If $x_1 = 8$ and $x_2 = 4$, then $x_3 + x_4 + x_5 = 8$.
  6. If $x_1 = 10$ and $x_2 = 5$, then $x_3 + x_4 + x_5 = 5$.
  7. If $x_1 = 12$ and $x_2 = 6$, then $x_3 + x_4 + x_5 = 2$.
$\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.