My problem is the following:
Input: a set of $m$ non-negative integers $\{b_1,...,b_m\}$ and a parameter $n$ with $n<m$.
Output: $n$ sets of 3 numbers
Task: Cut the $b_i$'s into $3n$ integers such that we can gather these numbers in $n$ sets of 3 elements where all the elements in a set are the same.
Example (with $m=4$ integers as input): $b_1=10$, $b_2=9$, $b_3=6$ ,$b_4=5$ and $n=3$.
For this instance, there is a solution since we can cut the $b_i$'s in the following way:
- $b_1=10=5 + 4 +1$
- $b_2=9=5 +4$
- $b_3=6=5+1$
- $b_4=5=4+1$
So the $n=3$ sets are $\{5,5,5\}$, $\{4,4,4\}$ and $\{1,1,1\}$.
My first question is: how could I show that my problem is NP-hard?
In order to move forward on this question, I thought about a reduction from a 3-PARTITION instance to an instance of my problem (but maybe this idea is not correct, see my second question).
Let $\{a_1,...,a_{3p}\}$ with $\sum_{i=1}^{p}a_i=pB$ be a general 3-PARTITION instance. From this instance of 3-PARTITION, I create an instance of my problem in the following way (see the example below):
We have $n=3p$ and there are $m=7p$ integers which are:
- $6p$ integers in this way: $b_1=b_{1'}=a_1$, ..., $b_{3p}=b_{3p'}=a_{3p}$
- $p$ integers in this way: $b_{3p+1}=...=b_{4p}=B$
W.l.o.g, suppose we have a solution of the instance of 3-PARTITION, $B=a_1+a_2+a_3=a_4+a_5+a_6=...=a_{3p-2}+a_{3p-1}+a_{3p}$, it is easy to construct a solution to the instance of my problem by only cutting the $p$ last integers equal to $B$, the cut is denoted $b_{3p+k}=B=b_{3p+k}^{(1)}+b_{3p+k}^{(2)}+b_{3p+k}^{(3)}$.
The solution of my problem is then composed of the $n=3p$ following sets:
- Set 1: $\{b_1,b_{1'},b_{3p+1}^{(1)}\}$, Set 2: $\{b_2,b_{2'},b_{3p+1}^{(2)}\}$, Set 3: $\{b_3,b_{3'},b_{3p+1}^{(3)}\}$
- ...
- Set 3p-2: $\{b_{3p-2},b_{3p'-2},b_{4p}^{(1)}\}$, Set 3p-1: $\{b_{3p-1},b_{3p'-1},b_{4p}^{(2)}\}$, Set 3p: $\{b_{3p},b_{3p'},b_{4p}^{(3)}\}$
And all the elements inside a set are the same since we have a solution to the 3-PARTITION instance.
So, with the previous construction, we have that: if there is a solution to the 3-PARTITION instance $\Rightarrow$ we have a solution to the instance of my problem.
My second question is: what about the other sense? Is it possible to show that if we have a solution to the instance of my problem, it implies that we have a solution of the original 3-PARTITION instance?
One way would be to show that the construction of the $3p$ sets as described above is the unique solution of the instance of my problem. This is the reason why, in the first place, in the instance of my problem, each integer is repeated twice.
Example of the reduction Consider the following instance of 3-PARTITION: $a=\{47,44,43,40,37,35,29,28,27\}$, we have $p=3$ and $\sum_i^9 a_i=3\times 110$.
The instance of my problem is then made of the following $m=21$ integers: $b=\{47,47,44,44,43,43,40,40,37,37,35,35,29,29,28,28,27,27,\color{red}{110},\color{blue}{110},\color{magenta}{110}\}$.
The solution of the 3-PARTITION instance $47+35+28=44+37+29=40+43+27=110$ implies this solution of the instance of my problem with $n=9$ sets:
- Set 1: $\{47,47,\color{red}{47}\}$, Set 2: $\{35,35,\color{red}{35}\}$, Set 3: $\{28,28,\color{red}{28}\}$
- Set 4: $\{44,44,\color{blue}{44}\}$, Set 5: $\{37,37,\color{blue}{37}\}$, Set 6: $\{29,29,\color{blue}{29}\}$
- Set 7: $\{43,43,\color{magenta}{43}\}$, Set 8: $\{40,40,\color{magenta}{40}\}$, Set 9: $\{27,27,\color{magenta}{27}\}$
This illustration shows that if we have a solution of the 3-PARTITION instance, then it is easy to build a solution of my problem.
In terms of this example, the question is: is it possible to show that if we have a solution to the instance of my problem
$b=\{47,47,44,44,43,43,40,40,37,37,35,35,29,29,28,28,27,27,\color{red}{110},\color{blue}{110},\color{magenta}{110}\}$, then we have a solution of the original 3-PARTITION instance (for this particular $b$, it is the case).
For the moment, I am trying to find a counterexample, that is, an instance of my problem for which we do have a solution but which does not imply a solution of the 3-PARTITION instance.
Thank you very much for your help!
