Given $(a_1,b_1,c_1), (a_2,b_2,c_2),\ldots, (a_n,b_n,c_n)$

We need to decide if there exists non-negative coefficients:

$X = (x_1,x_2,\ldots,x_n)$

such that

$$ x_1 a_1 + x_2 a_2 + \ldots + x_n a_n = x_1 b_1 + x_2 b_2 + \ldots + x_n b_n = x_1 c_1 + x_2 c_2 + \ldots + x_n c_n $$

How to do it efficiently?

The above problem is a part of my solution while solving the following ACM/ICPC problem

  • $\begingroup$ You might want to take algorithms questions to cs.SE. $\endgroup$ – Raphael Apr 8 '12 at 14:27
  • $\begingroup$ @mixedmath All he is requesting is nonnegativity. The knapsack problem requires nonnegative integers. If non integral solutions are allowed, this is not too difficult in theory (it is a linear programming feasibility problem). Some modification of the simplex algorithm should find a solution fairly rapidly. $\endgroup$ – deinst Apr 8 '12 at 17:33
  • $\begingroup$ Oh, non-integers. Well that's just silly. Then this is far more reasonable, you're right. $\endgroup$ – davidlowryduda Apr 8 '12 at 23:30

Trivially, $x_i=0$ is a solution, so I assume the problem is to find a solution where at least one of the $x_i$ is positive.

First consider the equation $$\sum_{i=1}^n a_ix_i = \sum_{i=1}^n b_ix_i.$$ If $a_i=b_i$ for all $i$, then this is trivially satisfied, otherwise there is some $i$ where $a_i\ne b_i$. Assume w.l.o.g. that $a_1\ne b_1$. Then $$x_1=\sum_{i=2}^n \frac{b_i-a_i}{a_1-b_1}x_i.$$ Now consider the equation $$\sum_{i=1}^n a_ix_i = \sum_{i=1}^n c_ix_i.$$ which, upon substitution for $x_1$ becomes $$\sum_{i=2}^n\left(a_i+\frac{b_i-a_i}{a_1-b_1}a_1\right)x_i=\sum_{i=2}^n\left(c_i+\frac{b_i-a_i}{a_1-b_1}c_1\right)x_i.$$ If these are equal, the equation is trivially satisfied, otherwise there is some index where $$a_i+\frac{b_i-a_i}{a_1-b_1}a_1\ne c_i+\frac{b_i-a_i}{a_1-b_1}c_1.$$ Assume w.l.o.g. that this index is $i=2$ This will allow us to find $x_2$ in terms of the other $x_i$'s, $i>2$, say $x_2=\sum_{i=3}^n d_i x_i$, and we can substitute this into our equation for $x_1$, giving us an equation for $x_1$ in terms of $x_3,\ldots,x_n$, say $x_1=\sum_{i=3}^n e_i x_i$.

If all the $d_i$ or all the $e_i$ are negative, then obviously there is no solution. Or if one is nonpositive and the other is negative when it is 0, there is no solution. Otherwise, if for some $i$ both $d_i$ and $e_i$ are nonnegative, then setting $x_i=1$ is a solution. So there are indices $i$ where $d_i>0$ and $e_i<0$, and indices $j$ where $d_j<0$ and $e_j>0$. If there are such $i$ and $j$ so that $\frac{e_j}{-e_i}>\frac{d_i}{-d_j}$ then there is a solution, otherwise not.


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.