When can $L$ sets of the form $\{a,b,a+b\}$ partition $\{1,2,\dots, 3L\}$?

Question

Firstly, this question has been posted to Math StackExchange with no complete answer so far.

Consider a set of the form $\{a,b,a+b\}$ where $a$ and $b$ are positive integers with $b > a$. I will refer to such a set as a triplet. Consider now the problem of constructing $L$ disjoint triplets with as small a maximum element across them as we can manage. I will refer to a collection of $L$ disjoint triplets having the smallest maximum element across them as optimal. At best, the triplets will partition $\{1,2,\dots,3L\}$ giving a lower bound of $3L$ on the maximum element. As noted in the Math StackExchange comments, this lower bound can be strengthened to $3L+1$ when $L \cong 2,3\text{ mod } 4$ since $1+2+\cdots+3L$ is odd while sums of triplets are even.

The interesting part is that it seems that these lower bounds are always achievable and have been verified by integer linear programming search as described in the Math StackExchange answer for $L\in\{1,2,\dots,100\}$.

Here are some examples:

For $L = 1$, we have $\{1,2,3\}$ achieving the lower bound of $3 = 3L$.

For $L=2$, we have $\{1,3,4\}$, $\{2,5,7\}$ achieving $7 = 3L+1$.

For $L=3$, we have $\{1,4,5\}$, $\{2,6,8\}$, $\{3,7,10\}$ achieving $10 = 3L+1$.

For $L=4$, we have $\{1,8,9\}$, $\{2,10,12\}$, $\{3,4,7\}$, $\{5,6,11\}$ achieving $12 = 3L$.

For $L=5$, we have $\{1,14,15\}$, $\{2,10,12\}$, $\{3,8,11\}$, $\{4,5,9\}$, $\{6,7,13\}$ achieving $15 = 3L$.

At the very least, can it be shown that for $L$ a multiple of $4$, we can always partition $\{1,2,\dots, 3L\}$ into $L$ sets of the form $\{a,b,a+b\}$?

Answer 1

Yes, it is always possible to achieve these exact bounds. This was done in a slightly different language in

Th. Skolem, "On Certain Distributions of Integers in Pairs with Given Differences", Mathematica Scandinavica 5 (1957), 57–68

For example, when $L=4k$ you can use the decomposition

• $(4k-2i,8k+i, 12k-i)$ for $0\le i\le 2k-1$
• $(4k-2i-1, 4k+i,8k-1-i)$ for $1\le i\le k-1$
• $(2k-2i-3, 5k+2+i,7k-1-i)$ for $0\le i\le k-3$
• $(1, 5k,5k+1), (2k-1, 6k, 8k-1)$ and $(4k-1, 6k+1, 10k)$

In order to translate Skolem's partition like the example I did above, write your triples in the form $(i,L+a_i, L+b_i)$ for $1\le i \le L$ and use the pairs $(a_i,b_i)$ from the paper above.