# Given $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|$

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?

$y_5$ is the "slack" variable; insisting it is nonnegative enforces that $x_4\le 32$.
• 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".
• 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? Sep 28, 2016 at 5:25