1
$\begingroup$

Given an equation $a_1 X_1 + a_2 X_2 + \cdots + a_n X_n = N$ where $a_1,a_2,\ldots,a_n$ are positive constants and each $X_i$ can take only two values $\{0,1\}$. $N$ is a given constant. How can we calculate the possible no of solutions of given equation ?

  • 0
    Well in general the number of solutions depends on all your parameters, but do you need bounds on the number of solutions or something? i.e. the best way to know it is to dumbly compute all possibilities... but that's just not brilliant, isn't it.2011-11-03
  • 0
    @PatrickDaSilva : "the best way to know it is to dumbly compute all possibilities..." This is not a good idea since N is very large.2011-11-03
  • 0
    So what do you need actually? Bounds? Or the exact number of solutions? That could be reaaaally hard.2011-11-03
  • 0
    I need exact number of solutions.2011-11-03
  • 0
    do you know the $a_i$? Because the answer depends a lot on them, probably more than on $N$. For example, with $a_i=2^i$ a simple reasoning shows that the answer is either $0$ or $1$, depending on which is bigger: $N$ or $2^n$. While with $a_1=1,...,a_n=1$ you will get $n$ chose $N$ solutions. And i assume all your numbers are probably integers....2011-11-03
  • 0
    yes, each ai will be less than 15 and N < 10^18 .2011-11-03
  • 0
    and what is $n$?2011-11-03

2 Answers 2