1
$\begingroup$

Q: Let $S=\{1,2,...,32\}$ and $T = \{(x_1, x_2,x_3,x_4)\in S^4|x_2 \geq x_1 +3, x_3 \geq x_2, x_4 \geq x_3 + 5\}.$ Find $|T|$.

Answer provided(Using method for finding number of integer solutions):

Note: $x_4 \leq 32$.

Let:

$$y_1 = \hspace{10mm}x_1 \geq 1$$

$$y_2=x_2 -x_1 \geq 3$$

$$y_3 = x_3 -x_2 \geq 0$$

$$y_4 =x_4 -x_3 \geq 5$$

So, $y_1 +y_2 + y_3 +y_4 + y_5 = 32, $ for $y_1 \geq 1, y_2 \geq 3, y_3 \geq 0, y_4 \geq 5, y_5 \geq 0$.

Hence, we have

$$|T|= number \hspace{1mm} of \hspace{1mm}integer \hspace{1mm}solutions $$ $$=H_r^n$$ $$= {{r+n-1}\choose r}$$ $$= {{32-1-3-5+5-1}\choose{32-1-3-5}}$$ $$={27 \choose 23}$$ $$= {27 \choose 4}$$ $$\hspace{150mm}_{Q.E.D}$$

Question is, I do not understand why we have to include a $y_5 \geq 0$ when there are only 4 variables. Why doesn't $y_i$ for $i = 1,2,3,4$ suffice?

$\endgroup$
1
$\begingroup$

$y_5$ is the "slack" variable; insisting it is nonnegative enforces that $x_4\le 32$.

$\endgroup$
3
  • $\begingroup$ I'm sorry but I do not get the meaning of a "slack" variable even after referring to Wiki as I have not yet learnt/ studied as far as optimization and linear programming. Is there a a more layman definition? $\endgroup$ – Stoner Sep 28 '16 at 3:58
  • $\begingroup$ Slack variable converts an inequality to an equality so that we can solve the system easily. Without $y_5$ you need to find solutions to an inequality. But with $y_5$, we have an inequality and one can use the standard techniques such as "stars and bars". $\endgroup$ – user348749 Sep 28 '16 at 4:05
  • $\begingroup$ Ah alright do you mean something along the lines of: $ y_1 + y_ 2 + y_3 + y_4 \leq 32$ and $y_5 \geq 0$ such that when the equations are combined together we will remove the inequalities and thus result in an equality relation such as: $y_1 + y_2 + y_3 + y_4 + y_5 = 32$? Am I right to say that? $\endgroup$ – Stoner Sep 28 '16 at 5:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.