1
$\begingroup$

Given a set of linear Diophantine Equations (LDE's), where each equation is one of the following form:

Let C be a positive integer constant. Also, the number of variables in each equation is exactly $C$.

  1. $a_i + b_i+c_i.....=C$ or
  2. $a_i+b_i+c_i.....=(C+1)$

For every such set of LDE problem instance, the problem is solvable iff, at least one such solution exists, such that each variable's assigned value in that solution is:

  1. $\leq C$.
  2. $\geq 0$

In other words, the solution if it exists is bounded by the constant $C$ and $0$.

Can someone help with the proof of the above statement (or counterexamples with some small $C$)?

$\endgroup$
  • $\begingroup$ I would like to know your feedback about my answer $\endgroup$ – G Cab Feb 13 '18 at 11:09
0
$\begingroup$

So, if I understood properly your exposition, the system can be written as $$ \left\{ \matrix{ x_{\,1} + x_{\,2} + \cdots + x_{\,c_{\,1} } = c_{\,1} + d_{\,1} \hfill \cr x_{\,1} + x_{\,2} + \cdots + x_{\,c_{\,2} } = c_{\,2} + d_{\,2} \hfill \cr \quad \quad \vdots \hfill \cr x_{\,1} + x_{\,2} + \cdots + x_{\,c_{\,n} } = c_{\,n} + d_{\,n} \hfill \cr} \right. $$ where $d_k \in \{0,1\}$.

Clearly we can always rearrange the rows by increasing $c_k$'s $$ \left\{ \matrix{ x_{\,1} + x_{\,2} + \cdots + x_{\,c_{\,1} } = c_{\,1} + d_{\,1} \hfill \cr x_{\,1} + x_{\,2} + \cdots + x_{\,c_{\,1} } + \cdots + x_{\,c_{\,2} } = c_{\,2} + d_{\,2} \hfill \cr \quad \quad \vdots \hfill \cr x_{\,1} + x_{\,2} + \cdots + x_{\,c_{\,1} } + \cdots + x_{\,c_{\,2} } + \cdots + \cdots + x_{\,c_{\,n - 1} } + \cdots + x_{\,c_{\,n} } = c_{\,n} + d_{\,n} \hfill \cr} \right. $$

and subtracting from each row the preceding one $$ \left\{ \matrix{ x_{\,1} + x_{\,2} + \cdots + x_{\,c_{\,1} } = c_{\,1} + d_{\,1} \hfill \cr x_{\,c_{\,1} + 1} + \cdots + x_{\,c_{\,2} } = \left( {c_{\,2} - c_{\,1} } \right) + d_{\,2} - d_{\,1} \hfill \cr \quad \quad \vdots \hfill \cr x_{\,c_{\,n - 1} + 1} + \cdots + x_{\,c_{\,n} } = \left( {c_{\,n} - c_{\,n - 1} } \right) + d_{\,n} - d_{\,n - 1} \hfill \cr} \right. $$

This is not, actually, a set of equations but a collection of $n$ independent equations, since the variables in each row are different from (i.e. not related to) those in the other rows.

Now, an equation of those, of the type $$ x_{\,1} + x_{\,2} + \cdots + x_{\,m} = m + \hat d\quad \left| {\;\hat d = - 1,0,1} \right. $$ can have solutions in which the various $x_k$ are not necessarily limited to the range $[0,m]$.

Thus your claim is not justified.

$\endgroup$

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.