1
$\begingroup$

Let's imagine you want to get a number $A$ from a set of number $M$. You might use only +/- between the numbers and your job is to determine, whether it's possible to get the result $A$ or not.

So let's say $A = 12$ and $M =\{ 3,4,5 \} $ then the solution is $3+4+5 = 12$. $-3-4-5 = -12$ so $-12 <= A <= 12$.

The number of possible ways is $2^n$ where $n$ is number of elements in $M$. I also know that if there is odd number of odd numbers, $A$ must be odd and the GCD of $M$ must be also denominator of $A$ and so on. But in case I'm given $100$ numbers, it's not possible to check every possible way.

With two numbers, like $M = \{ 3, 4 \} $, solving it for let's say $A = 1$ might be as simple as solving two variable equations:

$$x^2 + y^2 = 25$$

$$x + y = 1.$$

But with $3$ or more numbers, it's just two equations and many variables. Is there a way to determine, if $A$ is among those possibilities ?

$\endgroup$
  • $\begingroup$ Can we use the operation +- on the same numbers several times ? ie for $M = \{ 3,4\}$ can I take $9 = 3 + 3 + 3$ or $k 3 = 3 + ... + 3 $ ($k$ times ) ? $\endgroup$ – Digitalis Feb 20 at 13:29
  • $\begingroup$ @Digitalis No. Every number from M has to be used exactly once. $\endgroup$ – ShinobiUltra Feb 20 at 13:34
  • $\begingroup$ Exactly once ? Take $M = \{ 3, 4\}$ so $3$ is not valid ?!? $\endgroup$ – Digitalis Feb 20 at 13:45
  • 1
    $\begingroup$ @Digitalis sorry for late answer; no, you cannot get 3 by using 3 and 4. Only 7, -7 and 1, -1 (3+4, 3-4, -3+4, -3-4), nothing else. $\endgroup$ – ShinobiUltra Feb 20 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.