Two equations are given:

$a_{1}b_{1} + a_{2}b_{2} + \dots + a_{n}b_{n} = N$

$b_{1} + b_{2} + \dots + b_{n} = M$

and given is set of $a_{1}, a_{2}, \dots a_{n}$

$a_{1}, \dots, a_{n} \geq 0$ and $b_{1}, \dots, b_{n} \geq 0$

How to find all possible equations which satisfy these conditions?

For example:

$a + 2b + c = 5,$

$a+b+c = 4$

We have four combinations: (2,1,1), (1,1,2), (0,1,3), (3,1,0)

Is there any formula for that? What if there will be inequality $ \leq N$

  • $\begingroup$ not sure the combinatorics tag is needed ... the example has a countably infinite number of solutions on the integers, $\endgroup$ – user451844 Sep 20 '17 at 10:47
  • $\begingroup$ Oh... We can use only positive integers. $\endgroup$ – Piotr Wasilewicz Sep 20 '17 at 10:49
  • $\begingroup$ 0 is technically non-negative not positive, but okay that should be put in the question otherwise a+c=3 has a countably infinite number of solutions. $\endgroup$ – user451844 Sep 20 '17 at 10:51
  • $\begingroup$ Yes, thanks. I added this condition. $\endgroup$ – Piotr Wasilewicz Sep 20 '17 at 10:52

What we've got here is the system of 2 linear equations with $n$ unknown values. To solve it You can use for example the Gauss elimination.

In your example there are solutions with parametric form $$\begin{cases}a=t\\b=1\\c=3-t\end{cases}$$

In general there would be $n-2$ or $n-1$ parameters and there is no easy formula to compute the number of solutions.

There are some special cases when we can easily compute the number of solutions:

  • $a_1=...=a_n$ and $N\neq M\cdot a_1$ - then there are no solutions, because the system is conflicted
  • $n=2$ and $a_1\neq a_2$ - there is $1$ solution
  • $n=2$ and $a_1= a_2$ and $N=M\cdot a_1$ - there are $N$ solutions

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.