# Reducing partition to a partition where sum(partition1) = 3 times sum(partition2)

Given the following NP-complete problem:

PARTITION

Input: A list of positive integers $a_1, a_2, \dots, a_n$.

Question: Can the list be partitioned into $2$ parts, $A_1$ and $A_2$, such that the sum of each part is the same?

Now I want to reduce PARTITION to the following problem:

TRIPLE-SUM

Input: A list of positive integers $a_1, a_2, \dots, a_n$.

Question: Can the list be partitioned into $2$ parts, $A_1$ and $A_2$, such that the sum of the numbers in $A_1$ is exactly three times the sum of the numbers in $A_2$?

I'm struggling to see how the transformation can take place. I've tried transforming the list $a_1, a_2, \dots, a_n$ by multiplying each element by $3$ (stupid... I know...) but everything I tried failed. Is there a way to perform this reduction? Does it even require to modify the input list?

• Perhaps you should spend a few more days on this problem. Reductions can be tricky. You might want to take a look at the related problem of SUBSET-SUM. – Yuval Filmus Apr 16 '16 at 22:42
• I think there is a way to do the reduction by adding an additional number to the input. Just a single number. Maybe i'm telling you too much… – rotia Apr 18 '16 at 15:13
• @rotia: Clever. I figured out a much more complicated way that worked by adding n numbers very close to the original ones... – gnasher729 Oct 25 '16 at 17:54
• Our reference question may provide some inspiration. – Raphael Oct 25 '16 at 22:12
• @rotia Hmm, that makes me think - can we reduce PARTITION to DOUBLE-SUM? (Trying to add The Number in this case does not work) – MCT Oct 26 '16 at 1:39