0
$\begingroup$

I have a system of $4$ equations in $4$ variables:

\begin{align} x_1 + y_1 &= m\\ x_2 - y_1 &= n\\ x_1 - y_2& = o\\ x_2 + y_2 &= p\end{align}

$x_1, y_1, x_2, y_2$ are integer points on co-ordinate system (we need only positive points in the solution).

I want to have only the positive integer value for all the variables $(x_1, x_2, y_1, y_2)$.

Let's suppose \begin{align}m &= 3\\ n &= 10^9 - 1\\ o &= 10^9 - 3\\ p &= 2 \times 10^9 - 7\end{align}

So, the above equation get satisfied for the values:

\begin{align}x_1 &= -3\tag{here $x_1$ is negative}\\ x_2 &= 7\\ y_1 &= 6 \\ y_2 &= 0\end{align}

Whereas the following set of values also satisfies the equation:

\begin{align}x_1 &= 1\\ x_2 &= 3\\ y_1 &= 2\\ y_2 &= 4\tag{here none is negative}\end{align}

I just want to find out the solution which has non-negative integer values for all 4 variables (having $0$ in the solution set is fine, just avoid negative values) when $m, n, o$ and $p$ can be any given constant.

Conditions: \begin{align}0 \leq x_1 \leq x_2 \leq 10^9\\ 0 \leq y_1 \leq y_2 \leq 10^9\end{align}

$\endgroup$
1
  • $\begingroup$ I've edited your question to use MathJax instead of code for the equations. The above comment gives lots of help on this $\endgroup$
    – lioness99a
    Commented Feb 8, 2019 at 9:40

3 Answers 3

1
$\begingroup$

If you subtract eq. $3$ from eq. $1$, you get $$ y_1 + y_2 = m -o $$ If you subtract eq. $2$ from eq. $4$, you get $$ y_1 + y_2 = p-n $$ and therefore $m-o = p-n$. Similarly, of you add eq. 1 and 2, you get $$ x_1 + x_2 = m+n $$ and if you add eq. 3 and 4, you get $$ x_1 + x_2 = p+o $$ And therefore $m+n=p+o$. Your condition was that all the $x$'s and $y$'s have to be non-negative, so $$ m+n=o+p \geq 0 \qquad \text{and} \qquad m-o = p-n \geq 0 $$ Subtracting these from each other leads us to $m - p \geq 0$. The second equation then tells us $$ m-p = o-n \geq 0 \qquad \Rightarrow \qquad o\geq n $$ So now we have the conditions $$ m \geq p \qquad \text{and} \qquad o \geq n $$ in order for the $x$'s and $y$'s to be positive. Therefore, if these conditions are fulfulled, it's possible to choose values for the $x$'s and $y$'s so that they are positive.

$\endgroup$
1
  • $\begingroup$ That's fine. But the main thing is how to find the solution to the equations? $\endgroup$
    – Aman Gupta
    Commented Feb 8, 2019 at 10:02
1
$\begingroup$

Let's start with the linear equation system, forgetting the additional constraints for the moment.

Subtracting the third from the first equation gives

$$y_1+y_2=m-o,$$

while subtracting the second from the fourth gives

$$y_1+y_2=p-n.$$

So unless $m-o=p-n$ or equivalently $m+n=o+p$, your system doesn't have any solution.

So your equations are dependent on each other, and if we assume $m+n=o+p$ we can just remove one equation to get an equivalent system. I decided to remove the third equation, as that gets rid of the constant $o$ that is sometimes hard to distinguish from the number $0$.

$$\begin{array}{} x_1+y_1 & = & m \\ x_2-y_1 & = & n \\ x_2+y_2 & = & p \\ \end{array}$$

3 equations for 4 variables leaves one 'free choice' of a variable usually (unless there is even more dependence among the equations). So let's use $x_1$ as that variable.

The first equation immediately leads to

$$y_1=m-x_1,$$

then the second equation leads to

$$x_2=n+y_1=n+m-x_1,$$

and finally the third equation to

$$y_2=p-x_2=p-n-m+x_1.$$

If you fear that having removed the 3rd original equation has been an error, you can see that it still holds:

$$x_1-y_2=x_1-(p-n-m+x_1)=x_1-x_1+n+m-p=n+m-p=o,$$

taking into account the necessary condition $m+n=o+p$.

So back to the given constraints:

$0 \le x_1$ just becomes equivalently $x_1 \ge 0$.

$x_1 \le x_2$ becomes $x_1 \le n+m-x_1$, which is equivalent to $x_1 \le \frac{n+m}2$.

$x_2 \le 10^9$ becomes $x_1 \ge n+m - 10^9$.

Similiarly, $y_1 \ge 0$ becomes $x_1 \le m$, $y_1 \le y_2$ becomes $x_1 \ge m + \frac{n-p}2$ and $y_2 \le 10^9$ becomes $x_1 \le 10^9+n+m-p$.

That means all of your conditions are equivalent to

$$x_1 \ge \max\left\{0,n+m-10^9,m + \frac{n-p}2\right\}$$

and

$$x_1 \le \min\left\{\frac{n+m}2, m, 10^9+n+m-p\right\}.$$

So, always taking into account the necessary condition $m+n=o+p$, you can choose $x_1$ acording to those 2 inequalities, calculate $x_2,y_1,y_2$ according to the equations I gave above and get a solution that fulfills your other conditions as well.

$\endgroup$
5
  • $\begingroup$ That's awesome, thanks a lot! $\endgroup$
    – Aman Gupta
    Commented Feb 8, 2019 at 10:14
  • $\begingroup$ Try to redo the calculations. That may show where I made a clerical error (I hope not, but you never know) and it helps you actually understand the solution. $\endgroup$
    – Ingix
    Commented Feb 8, 2019 at 10:19
  • $\begingroup$ And how does the equation change when I need only integer values for x1 (and eventually for all) variables? $\endgroup$
    – Aman Gupta
    Commented Feb 8, 2019 at 10:33
  • $\begingroup$ It doesn't change, at least if $m,n,o,p$ are also integers. All the equations to calculuate $x_2,y_1$ and $y_2$ will give you integer results if you start with $x_1$ as integer. The inequality conditions also don't change, it may just happen that if the resulting max/min values come from the halve fractions, you must start with the next higher/lower integer. So if e.g. for a given parameter set we get for real $x_1$ the lowe bound $x_1 \ge 17.5$, that would need to be changed to $x_1 \ge 18$, and similar for the $x_1 \le ...$ case. $\endgroup$
    – Ingix
    Commented Feb 8, 2019 at 10:42
  • $\begingroup$ Okay, I get it. That's cool. $\endgroup$
    – Aman Gupta
    Commented Feb 8, 2019 at 10:43
0
$\begingroup$

Above equation shown below:

$\begin{align} x_1 + y_1 &= m\\ x_2 - y_1 &= n\\ x_1 - y_2& =\phi\\ x_2 + y_2 &= p\end{align}$

Solution is: $(x_1,x_2,y_1,y_2)=[(4),(p+\phi-4),(m-4),(p-m-n+4)]$

Where, $(m+n)=(p+\phi)$

For $(m,n,\phi,p)=(7,3,2,8)$ we get:

$(x_1,x_2,y_1,y_2)=(4,6,3,2)$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .