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

1 Answer 1

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

You must log in to answer this question.

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