Count the integer solutions of $x_1+x_2-x_3+x_4-x_5=3$

Question

I am asking for help with solving this exercise:

Find the count of possible integer solutions for equation:

$$x_1+x_2-x_3+x_4-x_5=3$$

There are restrictions for possible values of $x$:

$$ \begin{aligned} &0 < x_1 \le 6\\ -&8 \le x_2 < -2\\ &x_3 \le 1\\ &3 < x_4\\ &2 \le x_5 \le 8 \end{aligned} $$

Note: We should be able to find the count of solutions by using permutations and Inclusion-Exclusion principle.

Answer 1

As a simplification, transform$^\star$ $x_i$ to $y_i$ so that all variables are atleast positive.

$$y_1 + y_2 + y_3+y_4+y_5 = 15\\ y_1 \in [0,5]\\ y_2 \in [0,5] \\ y_3 \in [0,\infty] \\ y_4 \in [0, \infty] \\ y_5 \in [0,6] $$

Now the bounds in place, it is simple to use inclusion exclusion principle.

$$ \begin{align} N &= N_{y_i \in [0, \infty)} \\ &- (N_{y_1 > 5} + N_{y_2 > 5} +N_{y_5 > 6}) \\ &+(N_{y_1 > 5 \land y_2 > 5} + N_{y_2 > 5 \land y_5 > 6}+N_{y_1 > 5 \land y_5 > 6}) \\ &- (N_{y_1 > 5 \land y_2 > 5 \land y_5 > 6}) \end{align} $$

Now the rest is pretty straight forward using the classic stars and bars:

$$\binom{19}{4} - \left(\binom{13}{4} +\binom{13}{4} +\binom{12}{4} \right)+\left(\binom{7}{4} +\binom{6}{4} +\binom{6}{4} \right)-0 = \boxed{\color{maroon} {2016}}$$

---

Edit

$^\star$In this edit I try to explain how we can transform the $x_i$ to $y_i$

1. We start with $x_1 \in [1,6]$, so $x_1 - 1 \in [0,5] $

2. Now $x_2 \in [-8,-2)$ or $x_2+8 \in [0,5]$

3. $x_3 \in (-\infty, 1]$ or $-x_3 \in [-1, \infty)$ and $-x_3+1 \in [0, \infty)$

4. And then $x_4 \in [4, \infty)$ so $x_4-4 \in [0, \infty)$.

5. Lastly $x_5 \in [2,8]$ or $-x_5 \in [-8,-2]$ and $-x_5 + 8 \in [0,6]$

Now sum all the inequalities in the end of each numbered point. Call each expression in variable as new variable $y_i$. Required equation is:

$$(x_1 - 1) + (x_2+8) + (-x_3+1) + (x_4-4) + (-x_5+8 ) = 3 + (-1+8+1-4+8) \\ y_1 + y_2 + y_3 + y_4 + y_5 = 15$$

Answer 2

Hint: $-9\le a=x_1+x_2-x_5\le-5$; $b=-x_3+x_4\ge3$. Now you have 5 pairs of solutions $(-9,12),(-8,11),(-7,10),(-6,9),(-5,8)$. Let's start with $(-9,12)$.
$a=-9$ only when $x_1=1, \: x_2=-8, \: x_3=2$. Now $b=12$ when $x_3=-8, x_4=4$; $x_3=-7, x_4=5$; ..., $x_3=1, x_4=11$. That's 10 solutions. Can you finish?

Answer 3

I need help with solution too. On the picture is my try.

Answer 4

By translations $x\to x+c$ and symmetries $x\to-x$ you can reformulate your problem as

Find all $x_1,x_2,x_3,x_4,x_5$ integers that satisfy $$ 1+x_3+x_4 = x_1+x_2+x_5$$ with bounds $$0\le x_1\le 5\qquad 0\le x_2\le 5\qquad 0\le x_5\le 6$$ $$0\le x_3\qquad 0\le x_4$$

Now, call $p(n)$ the number of triples $(x_1,x_2,x_5)$ such that $x_1+x_2+x_5=n$ and such that $$0\le x_1\le 5\qquad 0\le x_2\le 5\qquad 0\le x_5\le 6$$ hold. In the same way, let $q(n)$ the number of couples $(x_3,x_4)$ such that $x_3+x_4=n$ and such that $$0\le x_3\qquad 0\le x_4$$ hold. Your solution is $$ p(1)q(0) + p(2)q(1) + p(3)q(2) + \dots + p(16)q(15). $$ We know that $q(n)=n+1$, but $p(n)$ is much harder to compute, and I think must be done by a computer.

---

Let's do it with permutations/inclusion-exclusion.

First of all, a Toy Problem

Find all $x_1,x_2,x_3,x_4,x_5$ positive integers that satisfy $$c+x_3+x_4 = x_1+x_2+x_5$$ where $c$ is an integer (may be negative) and with bound $$c + x_3+x_4\le n$$ where $n$ is a positive integer.

Like before, let $p(m)$ the number of triples $(x_1,x_2,x_5)$ such that $x_1+x_2+x_5=m$ and let $q(m)$ the number of couples $(x_3,x_4)$ such that $x_3+x_4=m$. We know that $$ p(m) = \frac{(m+2)(m+1)}2 = \binom{m+2}2 \qquad q(m) = m+1 = \binom{m+1}1 $$ The solution is $$TP(c,n) = q(-c)p(0) + q(1-c)p(1) + \dots +q(n-c)p(n) $$ $$ = \binom {1-c}1\binom 22 + \binom {2-c}1\binom 32 + \dots + \binom {n-c+1}1\binom {n+2}2 $$

---

If we return to our first problem, we can operate an inclusion-exclusion method.

• First of all, we notice that $x_1+x_2+x_5\le 16$, so we can consider the Toy Problem with $c=1$ and $n=16$, so we get $TP(1,16)$.
• We have to respect the bounds, though, so we have to subtract the wrong solutions. How many solution are there with $x_5>6$? If we substitute $x_5 = 7 +z_5$ we get again the Toy Problem with $$-6+x_3 + x_4 = x_1+x_2+z_5$$ so $c=-6$ and $n=16 -7=9$, so $TP(-6,9)$. If we do the same for $x_1,x_2$ we get $TP(-5,10)$ twice.
• Now we subtracted too much. For example we subtracted twice the (wrong) solutions with $x_1>5,x_2>5$ and we have to add them again. With the same substitutions as before, we get $TP(-11,4)$. Doing the same for the other couples, we get $TP(-12,3)$ twice.

The final answer is thus $$TP(1,16) - TP(-6,9) - 2\cdot TP(-5,10) + TP(-11,4) + 2\cdot TP(-12,3) $$

Answer 5

Note that the problem reduces to counting the solutions of $x_4-x_3=\alpha=3+a$, where $a=-x_1-x_2+x_5$. Now note that $a$ ranges between $-1$ and $15$, so that $\alpha$ takes on values between $2$ and $18$ respectively, which gives us $17$ different values for $\alpha$. With the constraints $x_4\ge4$ and $x_3\le1$ and the equation $x_4-x_3=\alpha$, it is possible to note that the number of solutions is finite.