0
$\begingroup$

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

  • 0
    Oh, non-integers. Well that's just silly. Then this is far more reasonable, you're right.2012-04-08

1 Answers 1

2

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.