Linear and Integer Programming

43 Views Asked by At

How many different solutions are there to the equation

$x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=16$

with the following constraints:

$x_{1}\geq 1$

$x_{2}\geq 2$

$x_{3}\geq 0$

$x_{4}\geq 3$

$x_{5}\geq 2$

$0\leq x_{6}\leq 1$

So far, how I've been approaching the question is: Let $y_{1}=x_{1}-1$, $y_{2}=x_{2}-2$, $y_{3}=x_{3}$, $y_{4}=x_{4}-3$, $y_{5}=x_{5}-2$. And then substitute the equations in for x to express the equation in terms of y. However, I do not how to format $x_{6}$, and I'm not quite sure the logic behind this solution

1

There are 1 best solutions below

0
On

You can use the generating function to solve the problem. First of all we use your transformation of the variables.

$y_1+1+y_2+2+y_3+y_4+3+y_5+2+x_6=16$

I do not replace the $x_6$. We can solve the two cases $x_6=0$ and $x_6=1$ separately as suggested from lulu. If $x_6=0$ we have

$y_1+1+y_2+2+y_3+y_4+3+y_5+2=16$

$y_1+y_2+y_3+y_4+y_5+8=16$

$y_1+y_2+y_3+y_4+y_5=8$

Then we are looking for the coefficient of $y^8$ at $(1+y+y^2+y^3+...)^5=\frac{1}{(1-y)^5}$. This is equal to

$$\sum_{k=0}^{\infty} \binom{k+4}{k} \cdot y^k$$

Therefore in case $x_6=0$ we have $\binom{8+4}{8}=\binom{8+4}{4}=495$ different solutions. Similar procedure for the case $x_6=1.$