# Given a set, partition it into ordered triples

I have a set $$S$$ of $$3m$$ positive numbers $$\{a_1,a_2,\ldots,a_{3m}\}$$.

The question is: can you select $$m$$ disjoint triples $$(a_i,a_j,a_k)$$ from $$S$$ such that $$a_i-a_j-a_k\geq1$$?

I was trying to prove that this problem is NP-hard by a reduction from Numerical 3D matching (N3DM).

Given an instance of N3DM; 3 sets $$X$$, $$Y$$, $$Z$$, and a bound $$b$$, normalize it to make $$b=1$$. I create an instance of my problem as follows: $$S=X\cup Y\cup Z$$ and for each $$x_i\in X$$, set $$a_i=x_i+3M$$, for each $$y_j\in Y$$, set $$a_j=2M-y_j$$, and for each $$z_k\in Z$$, set $$a_k=M-z_k$$. $$M$$ is chosen very large. The idea of this comes from https://cs.stackexchange.com/a/117122/48180.

If N3DM is solved, then $$x_i+y_j+z_k=1$$, thus $$a_i-a_j-a_k=1$$ and my problem is solved. But if my problem is solved I cannot prove that N3DM is solved because I could select for example two elements from the same set say $$Z$$, $$x_i+3M-M+z_j-M+z_k=M+x_i+z_j+z_k\geq1$$ but N3DM is not solved.

I was saying maybe the problem is easy after all?

Do you have any hints?

If you select two elements from $$Z$$, then by the pigeonhole principle, there must be a triple that does not contain any element from $$Z$$, which is impossible.
First, note that the $$m$$ $$a_i$$ values of triplets should be the $$m$$ largest values of $$S$$.
Then for the $$2 m$$ remaining values. Follow the decreasing $$a_i$$ and select the pair ($$a_j$$, $$a_k$$) among the remaining values to minimize $$D = a_i-a_j-a_k$$ respecting $$D \ge 1$$.
If you cannot there is no solution. This achieves a $$O(m^3)$$ time complexity.