[Math] Discrete Math – Finding the integer solutions of an inequality

combinatoricsdiscrete mathematicsinequality

For couple of hours I'm contemplating on this question:

How many non-negative integer solutions of the inequality $x_1 + x_2 + x_3 + \ldots + x_6 < 10$?

I've come up with a solution with the aid of my notes:

By adding x$_7$ which is greater than 0 we can rewrite as,

$x_1 + x_2 + x_3 + \ldots + x_6 +x_7= 10$ where $0 \leq x_i, \space 1 \leq i \leq 6$ and $0 < x_7$

so we can supply $y_i=x_i$ and $y_7=x_7 – 1$
Then the equation becomes, $$y_1+y_2+y_3 + \dots +y_6+y_7 = 9$$ This is $C(15, 9)$

Although it is all fine, the point that I couldn't understand is: Why are we supplying a new variable and subtracting $1$ from the one that we initially added in?

Best Answer

The argument boils down to the following:

Since $x_1+...+x_6$ is less that $10$, it is missing something from $10$. Denote this quantity by $x_7$. By doing this you transformed the inequality into an equation, which in this case (and actually often) is easier to solve than an inequality.

Now for the second part: since you need $x_1+...+x_6$ to be strictly less than $10$, it follows that $x_7 \geq 1$. But the technique which you learned (stars and bars probably) works for variables which are non-negative, it doesn't work with restrictions of this form . To fix this note that $x_7-1 \geq 0$, and denote this by a new variable.

It would had probably been more intuitive to observe that $x_1+..+x_6 <10$ in integers is equivalent to $x_1+..+x_6 \leq 9$. Now denote by $x_7$ (or $y_7$) the missing quantity from $9$, which could be $0$, and reduce the problem directly to the second equation.

Related Question