0
$\begingroup$

How many solutions does the equation $x_1 + x_2 + x_3$ = 11 have, where $x_1$ , $x_2$ and $x_3$ are nonnegative integers?

I was attempting to solve the problem by using the method of mutually exclusive cases ie setting $x_1$ to 1 and having $x_2$ 2 and ect but then online i see a lot of questions are utilizing the stars and bars method and I was wondering how to do that rather than just brute forcing the problem?

$\endgroup$

1 Answer 1

1
$\begingroup$

To solve the problem using mutually exclusive cases:

Notice that $x_1$ can assume each value between $0$ and $11$, inclusive.

If $x_1 = 0$, then $x_2 + x_3 = 11$. The equation $x_2 + x_3 = 11$ has $12$ solutions since $x_3 = 11 - x_2$ and $x_2$ can assume each of the $12$ values between $0$ and $11$, inclusive.

If $x_1 = 1$, then $x_2 + x_3 = 10$. The equation $x_2 + x_3 = 10$ has $11$ solutions since $x_3 = 10 - x_2$ and $x_2$ can assume each of the $11$ values between $0$ and $10$, inclusive.

More generally, if $x_1 = k$, $0 \leq k \leq 11$, then $x_2 + x_3 = 11 - k$. The number of solutions of the equation $x_2 + x_3 = 11 - k$ is $11 - k + 1 = 12 - k$ since $x_3 = 11 - k - x_2$ can assume each of the $12 - k$ values between $0$ and $11 - k$, inclusive.

Hence, the number of solutions of the equation $$x_1 + x_2 + x_3 = 11$$ in the nonnegative integers is $$\sum_{k = 0}^{11} (12 - k) = \sum_{j = 1}^{12} j = \frac{12 \cdot 13}{2} = 78$$

To solve the problem using combinations with repetition:

We wish to find the number of solutions of the equation
$$x_1 + x_2 + x_3 = 11$$ in the nonnegative integers. A particular solution corresponds to the placement of two addition signs in a row of eleven ones. For instance, $$1 1 1 1 + 1 1 + 1 1 1 1 1$$ corresponds to the solution $x_1 = 4$, $x_2 = 2$, $x_3 = 5$, while $$+ 1 1 1 + 1 1 1 1 1 1 1 1$$ corresponds to the solution $x_1 = 0$, $x_2 = 3$, $x_3 = 8$. Hence, the number of solutions of the equation in the nonnegative integers is the number of ways we can insert two addition signs in a row of eleven ones, which is $$\binom{11 + 2}{2} = \binom{13}{2} = 78$$ since we must choose which two of the $13$ positions (eleven ones and two addition signs) will be filled with addition signs.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .