2
$\begingroup$

The first equation is $m_1x_1 + m_2x_2 + \cdots + m_{n}x_{n} = K$, and then
$x_1 \geq x_2 \geq x_3 \geq \cdots \geq x_{n-1} \geq x_{n}$. Rather than solving is there any method which can tell me if this is solvable or not. All the numbers numbers are positive intgers or zero.

  • 0
    @Ross - Thanks. But my understanding is that for Chinese reminder you need to have more than one equality equation. How to handle inequality like this.2011-03-14

1 Answers 1

1

Response to comment-does that mean integers is the answer to my question: But CRT will tell you when it cannot be done. If all the $m_i$ share a common factor that $K$ does not, there is no solution. If $m_1$ and $K$ have no common factor, you can pick $x_2$ through $x_n$ arbitrarily (subject to your inequalities), and solve the equation mod $m_1$. If $x_1, decrease $x_2$ through $x_n$ by $m_1$ and increase $x_1$ appropriately and you will have an answer. If $m_1$ and $K$ do have a common factor, pick all the $x_i, i \gt 1$ to share that factor and it still works.

  • 0
    That is why I asked what the allowable values are. If you allow reals, $x_1=12/5, x_2=x_3=0$ is a solution. If you allow integers, $x_1=3,x_2=1,x_3=-6$ is a solution. In the positive integers, there is no solution with your ordering constraints. To put in the ordering constraints, you can define variables $y_i=x_i-x_{i+1}$ up to $y_{n-1}$ and keep $x_n$. Then all the variables just have to be $\ge 0$ and usual linear programming techniques apply.2011-03-15