# Combinatorics using Linear Transformation

Determine the number of integer solutions to $x_1+x_2+x_3+x_4 \le 72$ such that:

• $1 \le x_1 \le 12$
• $0 \le x_2\le 10$
• $3 \le x_3\le 13$
• $5 \le x_4\le 36$

At first, I introduced a variable $x_5$ such that $x_1+x_2+x_3+x_4+x_5=72$ and applied a linear transformation such that:

• $y_1 = x_1-1$
• $y_2 = x_2$
• $y_3 = x_3-3$
• $y_4 = x_4-5$
• $y_5 = x_5$

and then regarranging and substituting values into the original equation, I get $y_1+y_2+y_3+y_4+y_5=63$ such that:

• $y_1 \le 12$
• $y_2 \le 10$
• $y_3 \le 13$
• $y_4 \le 36$
• $y_5 \ge 0$

my instincts tell me I should apply another linear transformation, but I'm not quite sure how to go from here.

Any tips would be appreciated!

• What you've written makes no sense. Please edit the question to show us what linear transformation you applied and why you think that helped you on the way to a solution. – Ethan Bolker Feb 27 '18 at 23:44
• editied the approach – nickoba Feb 27 '18 at 23:50
• Hint: what's the maximum value of the sum? What restrictions (if any) does that impose on the values of the variables? – probably_someone Feb 27 '18 at 23:51

Any choice of $(x_1,x_2,x_3,x_4)$ that satify the constraints \begin{eqnarray*} 1 \le x_1 \le 12 \\ 0 \le x_2\le 10 \\ 3 \le x_3\le 13 \\ 5 \le x_4\le 36 \end{eqnarray*} will satify the constraint $x_1+x_2+x_3+x_4 \le 72$ so there are $12$ choices for $x_1$,$11$ choices for $x_2$,$11$ choices for $x_3$,$32$ choices for $x_4$, so there are $12 \times 11 \times 11 \times 32 = \color{red}{46464}$ solutions.