Sums of subsets

Call a set a $k-$ set if it contains $k$ elements. Call a set good if it satisfies the problem condition, and bad otherwise.

Note that any $n-$ set is good for $n \le 2$ .

The only $3 -$ sets that are bad are the sets containing elements $a < b < c$ such that $a + b = c$ . The only such sets are $(1, 2, 3), (1, 3, 4), (1, 4, 5), (1, 5, 6), (1, 6, 7), (1, 7, 8), (2, 3, 5), (2, 4, 6), (2, 5, 7), (2, 6, 8), (3, 4, 7), (3, 5, 8)$ , totaling up to $12$ sets.

Consider $n = 5$ . There are $2^5=32$ subsets. The maximum sum of these subsets is $4 +5+6+7+8 = 30$ , which allows for $30 - 0 + 1 = 31$ possible subset sums. Hence, by pigeonhole principle (pigeons are the subsets, holes are the sum of the subsets), there must be 2 sets with the same sum. This argument easily works for $n=6, 7, 8$ too.

Hence, we are left with the $n=4$ case.

[Note: What follows is an extremely lengthy case consideration, to show that there are only 10 good 4-sets. There are much faster ways to proceed, for example by considering the number of odd elements, or by considering the largest possible number. - Calvin ]

We will consider the pairs $(1, 8), (2, 7), (3, 6), (4, 5)$ , all of which have the same sum, to restrict the possibilities.

) If the four integers come from distinct pairs, i.e. exactly one integer is selected from each pair. The lonely triple $(1, 2, 3)$ discards two quadruples namely $(1, 2, 3, 4), (1, 2, 3, 5)$ . $(1, 2, 6, 4)$ is discarded by the lonely triple $(2, 4, 6)$ . $1, 2, 6, 5$ is discarded by $(1, 5, 6)$ . $(1, 7, 3, 4)$ is discarded by $(1, 3, 4)$ . $1, 7, 6, 5$ is discarded by $(1, 5, 6)$ . $(1, 7, 6, 4)$ is discarded by $(1, 6, 7)$ . $8, 2, 3, 5$ is discarded by the lonely triple $(2, 3, 5)$ . $(8, 2, 6, 4)$ is discarded by $(2, 4, 6)$ . $(8, 2, 6, 5)$ is discarded by $(2, 6, 8)$ . $(8, 7, 3, 4)$ , $(8, 7, 3, 5)$ are discarded by $(3, 4, 7), (3, 5, 8)$ respectively. $(8, 7, 6, 5)$ is discarded since $8 + 5 = 7 + 6$ . $(1, 7, 3, 5)$ is discarded since $1 + 7 = 3 + 5$ . It is easy to check the last two quadruples, $(8, 2, 3, 4)$ and $(8, 7, 6, 4)$ are good .

ii) If at least two of the integers come from the same pair.

Note that the following cases are not disjoint but it's alright as long as we count the overlapped good sets, since we covered all cases.

ii-a) If there exists a pair containing the two integers came from $(1, 8)$

Then $7$ is discarded. This leaves $2, 3, 4, 5, 6$ . Note that at most $1$ integer from each pair of consecutive integers can be chosen, i.e. from $(2, 3), (3, 4), (4, 5), (5, 6)$ . If $2$ is chosen, then $3$ is forbidden. So, we have to choose $4$ , $5$ or $6$ . $6$ clearly can't be selected. $5$ can't be chosen since $1 + 2 + 5 = 8$ . This leaves the set $(1, 2, 4, 8)$ , which can be easily checked to be good . If $4$ is chosen, then $3, 5$ must be discarded. We still have to choose the last element from $2, 6$ . $2$ returns to the last set, while $6$ gives $(1, 4, 6, 8)$ . If $3$ is chosen, then $2, 4$ are discarded. We have to choose one from $5, 6$ . $6$ clearly can't be chosen, so $5$ must be chosen. $(1, 3, 5, 8)$ is bad , so there are no solutions. The final set $(1, 5, 6, 8)$ is bad .

ii-b) If the exists a pair containing the two integers came from $(2, 7)$

Then $5$ is forbidden. This leaves $1, 3, 4, 6, 8$ . We need to choose two from these $5$ . If $1$ is chosen, then $3, 8$ are discarded. Also note that at most one from $(4, 6)$ can be chosen. Thus, the only possible sets are $(1, 2, 4, 7), (1, 2, 6, 7)$ . All these sets are bad since $1 + 2 + 4 = 7, 1 + 7 = 2 + 6$ . If $3$ is chosen, $1, 4$ can't be chosen. We have to choose one from $6, 8$ , but these two clearly can't be chosen. If $4$ is chosen, then $1, 3, 6$ can't be chosen, leaving $8$ . The set $(2, 4, 7, 8)$ is good , so we have $1$ good set. $6, 8$ can't be chosen simultaneously, a we're done.

ii-c) If there exists a pair containing the two integers came from $(3, 6)$

Then, we have to choose two integers from $(1, 2, 4, 5, 7, 8)$ . There are just ${6 \choose 2} = 15$ pairs, so we can check them manually. We'll just call the pair chosen bad if the quadruple is also bad for convenience. $(1, 2), (1, 4), (1, 5), (1, 7), (1, 8)$ are bad , the last one is bad because $1 + 8 = 3 + 6$ . $(2, 4), (2, 5), (2, 7), (2, 8)$ are also bad . $(2, 7)$ is bad since $2 + 7 = 3 + 6$ ). $(4, 5), (4, 7)$ are bad . One can easily check that $(3, 4, 6, 8)$ is good . $(5, 8)$ is bad . This leaves $(3, 6, 7, 8)$ and $(3, 6, 5, 7)$ , which are both good . Thus, there are a total of $3$ good sets in this case.

ii-d) If there exists a pair containing the two integers came from $(4, 5)$

Then, $1$ is discarded. So we have to choose the last two integers from $(2, 3, 6, 7, 8)$ . $(2, 3), (2, 6), (2, 7)$ are bad . $(3, 6), (3, 7), (3, 8)$ are bad . $(6, 7)$ is bad . $(7, 8)$ is bad . We're left with $(2, 4, 5, 8), (4, 5, 6, 8)$ , which are good .

In conclusion, the only good $4-$ sets are $(1, 2, 4, 8), (3, 4, 6, 8), (3, 6, 7, 8), (3, 5, 6, 7), (2, 4, 5, 8), (4, 5, 6, 8), (2, 3, 4, 8), (4, 6, 7, 8), (1, 4, 6, 8), (2, 4, 7, 8)$ .

Thus, there are $10 + {8 \choose 0} + {8 \choose 1} + {8 \choose 2} + {8 \choose 3} - 12 = \boxed{91}$ good sets.

Let $S$ be a subset of $R = \{1,2,3,4,5,6,7,8\}.$ If $\vert S \vert = 5$ then $S$ has $2^5 = 32$ subsets, but the largest sum that any subset can have is $4 + 5 + 6 + 7 + 8 = 30$ , and the smallest is $0,$ so there are only 31 possible values the sum can take, but 32 sums, so some sum would occur twice. If $\vert S \vert \geq 6$ then some pair of subsets of size at most 5 will have the same sum.

If $\vert S \vert \leq 2$ then all subsets must have distinct sums. There are $\binom{8}{0} + \binom{8}{1} + \binom{8}{2} = 37$ such sets.

Consider when $\vert S \vert = 3.$ If this set does not have distinct subset sums, then $S = \{a,b,c\}$ with $a + b = c.$ We will count the number of such triples. For any pair of numbers $x < y \in R,$ the set $\{x,y, y - x\}$ does not have distinct subset sums. There are $\binom{8}{2} = 28$ such pairs $x,y.$ Notice that any set $S = \{a,b,c\}$ with $a + b = c,$ is counted twice in these pairs, since it is counted when $x = a, y = c$ and when $x = b, y = c.$ We also get 4 sets of the form $\{x,x,y\}$ which are not subsets of $R$ . Thus, there are $\frac{28 - 4}{2} = 12$ subset of $R$ with size 3 that do not have distinct subset sums, and $\binom{8}{3} - 12 = 44$ that do.

When $\vert S \vert = 4$ , we consider cases based on how many odd elements are in $S$ . We can easily see that if all the elements of $S$ have the same parity, then $S$ does not have distinct subset sums. When $S$ has a single odd element $x$ , $S$ will have distinct subset sums if and only if $S - \{x\}$ has distinct subset sums. Such an $S$ cannot contain both 2 and 6, since then either 4 or 8 would mean not having distinct subset sums. Thus, the possibilities are $\{x,2,4,8\}$ and $\{x,4,6,8\}.$ For any odd $x$ these both have distinct subset sums, giving 8 such sets.

When $S$ has at least two odd elements, we compile the following table of possible pairs of odd elements and which even elements cannot occur with these.

$\begin{array}{cc} \{1,3\} & \{2,4\}\\ \{1,5\} & \{4,6\}\\ \{1,7\} & \{6,8\}\\ \{3,5\} & \{2,8\}\\ \{3,7\} & \{4\}\\ \{5,7\} & \{2\}\\ \end{array}$

When $S$ has exactly two odd elements, for each of the four rows of the table, if we suppose the pair of even elements not in the row are in $S$ , then we do not have distinct subset sums. For $\{3,7\}$ only $\{6,8\}$ works, and for $\{5,7\}$ no pair works.

When $S$ has 3 odd elements, we find that any set containing $1$ and 2 other odd numbers excludes all even numbers. The set $\{3,5,6,7\}$ does work, and no other even number can replace the $6.$

This gives a total of $37 + 44 + 8 + 1 + 1 = 91$ subsets of $R$ having distinct subset sums.