# #StackBounty: #reductions #partitions Reduction from 3-partition to ABC-partition

### Bounty: 50

The ABC-partition problem is a variant of 3-partition in which, instead of a single set $$S$$ with $$3 m$$ positive integers, there are three sets $$A, B, C$$ with $$m$$ positive integers in each. The goal is to construct $$m$$ triplets with the same sum, each of which contains exactly one integer from $$A, B$$ and $$C$$.

Here is a reduction from ABC-partition to 3-partition. Given the sets $$A, B, C$$ and the target sum $$T$$, construct a set $$S$$ as the union of the following sets:

• $${1000a+100 | ain A}$$
• $${1000b+10 | b in B}$$
• $${1000c+1 | cin C}$$

and the target sum $$1000T + 111$$. Obviously, every solution of $$A,B,C$$ is a solution of $$S$$. Conversely, in every solution of $$S$$, there must be exactly one element that ends with 100, one that ends with 10, and one that ends with 1; therefore, it corresponds to a solution of $$A,B,C$$.

Question: what is a reduction from 3-partition to ABC-partition?

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.