Given a set $U=\{1,2,3,...n\}$. How to partition elements in $U$ into sets $A$ and $B$ such that the sum of the elements in $A$ and $B$ is in minimum.

Question

I came across a particular problem wherein I think the answer would necessitate me to partition $U=\{1,2,3,...n\}$ into subsets $A$ and $B$ such that the sum of the elements in $A,B$ is at minimum.

To show that it is in minimum, the following should hold:

Let:

$sumA$ be the sum of the elements in $A$

$sumB$ be the sum of the elements in $B$

Then $sumA,sumB$ is at $minimum$ when $|sumA-sumB|$ is at $minimum$.

Possible Cases:

We are actually looking for all subsets of $U$. The number of subsets of $U$ is $2^n$.

Example: Let $U$={1,2,}. Then the number of subsets are $2^2=4$:

$\{1,2\}$,$\{1\}$,$\{2\}$,$\{\}$

We will drop $\{1,2\}$,$\{\}$ since they irrelevant to our task. So there should be $2^n-2$ possible subsets to be paired, in this case $\{1\}$,$\{2\}$.

Let $p$ be the possible subsets, then: $$p=2^n-2$$

The number of ways to arrange these subsets into $2$ sets is $p\cdot\ (p-1)=2^n-2 \cdot\ (2^n-3)$.

Problem: My problem is to figure out what will be the exact combination of subsets $A,B$ such that $sumA$ and $sumB$ is at the minimum. Any help would be very helpful.

Answer 1

Split them into consecutive groups of $4$ starting with the largest ( so the first block is $\{n-3,n-2,n-1,n\}$ ) and in each group $\{a,a+1,a+2,a+3\}$ split them so $a$ and $a+3$ are in $A$ and $a+1$ and $a+2$ are in $B$.

If the number of elements is a multiple of $4$ we are done.

If the remainder is $1$ put $1$ in $A$.

If the remainder is $2$ put $1$ in $A$ and $2$ in $B$.

If the remainder is $3$ put $1$ and $2$ in $A$ and $3$ in $B$.

It is not hard to see this is optimal.

Answer 2

Using your notation we immediately see that sumA + sumB = sumU. Ideally, we want sumA = sumB because then both are minimum. There are numerous ways of doing this, so here is one way. Set R = n mod 4. If n is divisible by 4 then R is zero. Otherwise, R is either 1, 2, or 3. Now consider the set {R+1, R+2, R+3, … n-1, n}. We can pair these up by matching the first and last and placing alternate pairs in set A and set B. This will give identical sums in both sets of (n+R)(n+R+1)/4 for each set. This leaves us with the first R elements which also need to be allocated. There are four cases to consider:

R = 0 - nothing left to allocate

R = 1 - place the remaining "1" in either set and the difference is just 1

R = 2 - place the remaining "1" in one set and the "2" in the other set and the difference is still only 1.

R = 3 - place "1" and "2" in one set and "3" in the other set and both sums are the same.