Skip to main content
1 of 3

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

Firstly, this question has been posted to Math StackExchange with no 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 $12 = 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\}$?