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?

Question

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?

Stefan4024 · Accepted Answer · 2016-11-01T18:18:19.790

5

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$

edited Nov 01 '16 at 18:18

answered Nov 01 '16 at 18:06

Stefan4024

35,843

Still confused :( ... – Hazem Alabiad Nov 01 '16 at 18:10
@HazemAlabiad I will elaborate more in a second – Stefan4024 Nov 01 '16 at 18:13
@HazemAlabiad You can check the update. I hope it will be much clearer now. – Stefan4024 Nov 01 '16 at 18:18
Yeah ... Thanks .... – Hazem Alabiad Nov 01 '16 at 18:25

Neel Sandell · Answer 2 · 2021-12-01T03:17:24.023

First, observe that there are now more solutions to the inequality. When we add the dummy variable, we know introduce a degree of freedom to help account for this new solutions.

Let's try and understand the equation $x_1 + x_2 + x_3 = 11$.This tells us that we have to equal 11, but when we introduce the inequality, we know have to account for $x_1 + x_2 + x_3 = 10$, $x_1 + x_2 + x_3 = 9$, all the way until ... $x_1 + x_2 + x_3 = 0$. How do we account for these? Well, we can introduce another variable that helps us "move" our original fixed value of 11.

Let's define $x_4$ to be greater than or equal to 0. How does this help us? If the first three equal 11, then the fourth will equal 0, if the first three equal 10, then the fourth will equal 1. and so on...

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?

2 Answers2