4
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ what kind of numbers are you searching for? integers? $\endgroup$ – Dr. Sonnhard Graubner Jan 6 '18 at 12:37
  • $\begingroup$ Yes, I am looking only for count of integer solutions $\endgroup$ – zdarsky.peter Jan 6 '18 at 12:38
  • $\begingroup$ there are a lot of solutions $\endgroup$ – Dr. Sonnhard Graubner Jan 6 '18 at 12:43
  • $\begingroup$ how can i send them to you? $\endgroup$ – Dr. Sonnhard Graubner Jan 6 '18 at 12:44
  • 1
    $\begingroup$ For reference, the answer I found using computer is $2016$ $\endgroup$ – jonsno Jan 6 '18 at 13:33
3
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ @Abcd Thanks mate I was going to link this problem to you! $\endgroup$ – jonsno Jan 6 '18 at 18:11
  • $\begingroup$ Can you tell me how you got $\dbinom{13}{4}$ for $y_1>5$? $\endgroup$ – Archer Jan 6 '18 at 18:57
  • $\begingroup$ @Abcd In that case we have $y_1 \in [6, \infty)$ so $y_1 - 6 \in [0,\infty)$, so that $(y_1 - 6) + y_2 + y_3 + y_4 + y_5 = 15-6 = 9 $. Answer is from stars and bars, since all terms are non negative $\binom{9+5-1}{5-1}$ $\endgroup$ – jonsno Jan 6 '18 at 19:02
  • $\begingroup$ @samjoe Your math works, thank you so much! $\endgroup$ – zdarsky.peter Jan 6 '18 at 21:22
1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ I think your boundaries are different then from @Manish Kundu $\endgroup$ – zdarsky.peter Jan 6 '18 at 13:21
  • $\begingroup$ no, since $2+n\le 1$ and $4+n>3$, so $-1 <n\le -1$ $\endgroup$ – Exodd Jan 6 '18 at 14:28
0
$\begingroup$

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

enter image description here

$\endgroup$
2
  • 6
    $\begingroup$ Welcome to MSE. Please type your questions (using MathJax) instead of posting links to pictures. $\endgroup$ – José Carlos Santos Jan 6 '18 at 13:27
  • $\begingroup$ It is kinda the way how I wanted to be solved, but I think that answer is not correct. $\endgroup$ – zdarsky.peter Jan 6 '18 at 13:41
0
$\begingroup$

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) $$

$\endgroup$
2
  • $\begingroup$ We should be able to find the count of solutions by using permutations and Inclusion–exclusion principle $\endgroup$ – zdarsky.peter Jan 6 '18 at 13:33
  • 1
    $\begingroup$ Ok, now I'll write it. Warning: it'll be long $\endgroup$ – Exodd Jan 6 '18 at 13:49
0
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ False: $x_4 = 3+ x_5+x_3 -x_1-x_2 \le 3+8+1-0+8=20$ $\endgroup$ – Exodd Jan 6 '18 at 12:59
  • $\begingroup$ Oh, yes. One has to consider $x_3$ too. $\endgroup$ – Allawonder Jan 6 '18 at 13:00
  • $\begingroup$ There is no infinite solutions, $x_4$ is bounded below but $x_3$ is positive at some point. $\endgroup$ – Abr001am Jan 6 '18 at 13:10
  • $\begingroup$ Still false: $x+y=\alpha$ has finite solutions when, for example, $x\ge 0$ and $y\ge 0$. $\endgroup$ – Exodd Jan 6 '18 at 13:11
  • $\begingroup$ There are actually infinitely many solutions. See new edition. $\endgroup$ – Allawonder Jan 6 '18 at 14:02

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.