Can you convert a packing with overlap to a packing without overlap?

134 Views Asked by At

There is a finite set $X$ of positive integers, and an integer $M$. A subset of $X$ is called packable if its sum is at most $M$.

Suppose there are $2 n$ packable subsets of $X$, such that each element of $X$ appears in exactly two subsets.

Is it possible to partition $X$ into $n$ packable subsets, such that each element of $X$ appears in exactly one subset?

Example

Suppose $n=2$ and $M=20$ and the $2 n$ packable subsets are $\{10,5,2\}$, $\{10,6,3\}$, $\{11,5,3\}$, $\{11,6,2\}$. Note that every two subsets intersect, so we cannot just pick two out of four subsets. However, we can partition all integers into two disjoint packable subsets $\{10,6,3\}$ and $\{11,5,2\}$.

Is it always possible?