Number of combinations for which $x_1+x_2+x_3=100$ if for every $3\ge i\ge 1$, $x_i$ is a non negative integer with $40\ge x_i$

arithmetic-progressionscombinatoricsinclusion-exclusion

I recently came across the following question:

Find the number of combinations for which $x_1+x_2+x_3=100$ if for every $3\ge i\ge 1$, $x_i$ is a non negative integer with $40\ge xi$.

I solved it in the following way, splitting it up into different instances

If $x_1=20$: 1 solution ($x_2=40, x_3=40$)

If $x_1=21$: 2 solutions

If $x_1=22$: 3 solutions

$\ldots$

If $x_1=40$: 21 solutions

As the resulting total is the addition of an arithmetic progression, we have $1+2+\ldots+21=\frac{(1+21) \cdot 21}{2}=\frac{21 \cdot 22}{2}=231$

I found this question in a chapter relating to the inclusion-exclusion principle, however I can't think of how to solve it using the inclusion exclusion principle. Could someone please show me a neat solution of this question with the use of the inclusion-exclusion principle, explaining also how he intuitively thought of going on to each step?

Best Answer

A particular solution of the equation $$x_1 + x_2 + x_3 = 100 \tag{1}$$ corresponds to the placement of $3 - 1 = 2$ addition signs in a row of $100$ ones. For instance, if we place the addition signs after the $20$th and $60$th ones, we obtain the solution $x_1 = 20$, $x_2 = 40$, $x_3 = 40$ (count the number of ones to the left of the first addition sign for the value of $x_1$, between the two addition signs for the value of $x_2$, and to the right of both addition signs for the value of $x_3$). Therefore, the number of solutions of the equation in the nonnegative integers is $$\binom{100 + 3 - 1}{3 - 1} = \binom{102}{2}$$ since we must choose which two of the $102$ positions required for $100$ ones and two addition signs will be filled with addition signs.

From these, we must subtract those cases in which one or more of the variables exceeds $40$.

A variable exceeds $40$: There are three ways to choose which variable exceeds $40$. Suppose it is $x_1$. Then $x_1' = x_1 - 41$ is a nonnegative integer. Substituting $x_1' + 41$ for $x_1$ in equation 1 yields \begin{align*} x_1' + 41 + x_2 + x_3 & = 100\\ x_1 + x_2 + x_3 & = 59 \tag{2} \end{align*} Equation 2 is an equation in the nonnegative integers with $$\binom{59 + 3 - 1}{3 - 1} = \binom{61}{2}$$ solutions. Hence, there are $$\binom{3}{1}\binom{61}{2}$$ solutions in which the value of a variable exceeds $40$.

However, if we subtract this amount from the total, we will have subtracted each case in which two variables exceed $40$ twice, once for each way of designating one of those two variables as the variable that exceeds $40$. We only want to subtract such cases once, so we must add them to the total.

Two variables exceed $40$: There are $\binom{3}{2}$ ways to select which two variables exceed $40$. Suppose they are $x_1$ and $x_2$. Then $x_1' = x_1 - 41$ and $x_2' = x_2 - 41$ are nonnegative integers. Substituting $x_1' + 41$ for $x_1$ and $x_2' + 41$ for $x_2$ in equation 1 yields \begin{align*} x_1' + 41 + x_2' + 41 + x_3 & = 100\\ x_1' + x_2' + x_3 & = 18 \tag{3} \end{align*} Equation 3 is an equation in the nonnegative integers with $$\binom{18 + 3 - 1}{3 - 1} = \binom{20}{2}$$ solutions. Hence, there are $$\binom{3}{2}\binom{20}{2}$$ solutions in which two variables exceed $40$.

Thus, by the Inclusion-Exclusion Principle, the number of solutions of equation 1 in which no variable exceeds $40$ is $$\binom{102}{2} - \binom{3}{1}\binom{61}{2} + \binom{3}{2}\binom{20}{2} = 231$$ as you found.

Related Question