How many solutions are there to the inequality $x_1 + x_2 + x_3 \le 11$ where $x_1,x_2,x_3$ are nonnegative integers?

Hint: introduce a variable $x_4$ such that $x_1 + x_2 + x_3 + x_4 = 11$.

Solution: $x_4$ is nonnegative, same as count the number of nonnegative solutions to the equality. It is $\binom{4+11-1}{11} = \binom{14}{3} = 364$

Why did we introduce an extra variable $x_4$? While if we have ($x_1 + x_2 + x_3 = 11$ ) we do not?

Solution 1:

Note that $x_1 + x_2 + x_3$ might be less than $11$ and it will still be one solutions to the inequality. To make up fo the difference between $x_1 + x_2 + x_3$ and $11$ we add a dummy variable, which is guaranteed to be positive.

We'll prove that there's $1-1$ correspondence between the solutions of $x_1 + x_2 + x_3 \le 11$ and $x_1 + x_2 + x_3 + x_4 = 11$.

Assume that $a_1 + a_2 + a_3 + a_4 = 11$ is a solution for the equation, then we have that $a_1 + a_2 + a_3 = 11 - a_4 \le 11$. This means that every solution to the equation we generates a solution to the inequality.

Now assume that $a_1 + a_2 + a_3 \le 11$ is a solution for the equation. Then obviously we can add $a_4 = 11 - a_1 - a_2 - a_3 \ge 0$ to the equation and we'll obtain a solution for the equation.

Note that each of this equations is uniquely determined, which means that the the $1-1$ relation is established. Hence the number of solutions of $x_1 + x_2 + x_3 \le 11$ is the same as the number of solutions of $x_1 + x_2 + x_3 + x_4 = 11$