Unique Sums

Let the eight pairs be $\{a_{1},a_{1}+b_{1}\},\{a_{2},a_{2}+b_{2}\},\{a_{3},a_{3}+b_{3}\},...,\{a_{8},a_{8}+b_{8}\}$ , where $b_{1},b_{2},b_{3},...,b_{8}$ are positive integers.

The sum obtained by choosing one integer from each pair is equal to the sum obtained from $\{0,b_{1}\},\{0,b_{2}\},\{0,b_{3}\},...,\{0,b_{8}\}$ plus $a_{1}+a_{2}+a_{3}+...+a_{8}$ .

The lowest possible sum of the $16$ integers can be found when $b_{1},b_{2},b_{3},...,b_{8}$ are equal to the minimum powers of $2$ - i.e. $1, 2, 4, 8,...,128$ .

Then we need to find $a_{1},a_{2},a_{3},...,a_{8}$ . Setting them as the first eight natural numbers would not work, but they can be $1,2,3,4,5,6,7,9$ . In this case, the eight pairs would be:

$\{7,8\},\{9,11\},\{6,10\},\{5,13\},\{4,20\},\{3,35\},\{2,66\},\{1,129\}$

Giving the sum of $\boxed{329}$ .

I originally misread the question (the question is clearly stated, that is my own fault) in that I was looking for 256 distinct sums of the subsets when the 16 integers are separated into pairs (including the zero subset and subsets of single integers). Meaning you separate into 8 pairs and choosing an integer from each pair produces 256 distinct values for the subsets. That is an interesting question in itself to find the lowest possible sum of a1, a2,....,a16.

Anyway, when I finally figured out what the question was here I looked at the most optimal set of sums when we have 3 pairs.

I found two ways to arrange the pairs with integers 1 to 6. {1,6} {2,5} {3,4} and {1,3} {2,6} {4,5}.

The latter is the more optimal.

In the latter pairing the 8 sums produced are consecutive integers (7,8,9,10,11,12,13,14).

Whereas in the former pairing the sums produced are not consecutive (6,7,9,10,11,12,14,15).

Therefore considering the most optimal pairing with 3 pairs we can make a logical guess of what the most optimal would be with 4 pairs.

We would convert {1,3} {2,6} {4,5} to {2,4} {3,7} {5,6} and add {1,9} as the next pair. This would give us 16 consecutive sums for 4 pairs. Therefore we can continue this process.

So for 5 pairs we would convert {1,9} {2,4} {3,7} {5,6} to {2,10} {3,5} {4,8} {6,7} and we would add {1,17} as our 5th pair.

So by the 8th pair we have {1,129} {2,66} {3,35} {4,20} {5,13} {6,8} {7,11} {9,10}