Question about numbers

Question

it's a task, on which i think during whole day.
i have four integer numbers a, b, c, d, and integer x[1,40].

---

i must write a program, which can find the values of {a,b,c,d}, for which one of following equations is true for any 1<=x<=40

    x=a or
    x=b or
    x=a+b or
    x=a+b+c+d or
    x+a=c+d or
    x+a+b=c+d or
    ...
    x+a+b+c=d or ... 

it is very difficult to explain what i want to say. maybe the example will be helpful.

example:

if x=17, by {a=1,b=2,c=5,d=15} i can write x+a+b=c+d
whole question is to present any x[1,40] by {a,b,c,d}.
hope that you understand what i want to say, and thanks in advance

UPDATE:

and there is only one solution, i'm sure, and i think, that

{a=1;a+b+c+d=40}

Answer 1

This is called the set partition and kinda subset sum problem which are NP Complete problems. i.e: this is a hard problem and your best bet is to use a brute force approach or a dynamic programming approach. in either case there is no "efficient" algorithm to solve this in linear time. at least no one knows for now.

http://en.wikipedia.org/wiki/Partition_problem

http://en.wikipedia.org/wiki/Subset_sum_problem

It might be related to game theory, but still this is a NP problem.

Answer 2

Actually here is nothing connected with programming. It is a pure mathematics. The algorithm of solving such tasks is simple. Starting from 1 we take the next biggest value possible so, that we can get all the other numbers up to sum(1..it) using only + and -.

So the first is 1.

The second will be 3, as 1 = 1, 2 = 3 - 1, 3 = 3, 4 = 3 + 1.

The 3rd is 9.

And you see the coincidence every next number id 3x previous. The four numbers you are looking for are {1, 3, 9, 27}, and you can get any number between 1 and 1 + 3 + 9 + 27 = 40 with them.

Answer 3

This is actually a case of balanced ternary location. For each of a, b, c, and d, you can either add it to the total, subtract it (because x + a + b == c + d is exactly the same as x == c + d - a - b, or leave it out. The numbers you want are therefore the ternary digit values, or 1, 3, 9, and 27.