Given a set, partition it into ordered triples

Question

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?

Answer 1

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.

Answer 2

I think there is a greedy way to solve this.

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.