Distinct sum subsets

56

The smallest possible sum is 0 and the largest possible sum is 55. If all sums in [0,55] were possible, the answer would be 56. We can prove that this is indeed the case.

Suppose that N is the smallest sum > 1 that cannot be obtained. By definition, the sum N-1 can be obtained. Let T be a subset of S={1,2,3...10} that sums up to N-1.

If 1 ∉ T, then T ∪ {1} has sum N and we are done. Otherwise, let n be the smallest natural number not present in T. This implies that n-1 ∈ T. If n∈S, we would obtain that {n}∪T/{n-1} has sum N.

Hence, the only way that a sum of N cannot be obtained is if n∉S. This would require that n=11, and hence T=S. That is, the smallest sum that cannot be obtained is 56.

Let S(x) denote the possible sums where x is the number of elements in the subset.

S(0) = 0

1 \leq S(1) \leq 10

(1 + 2) \leq S(2) \leq (9 + 10)

We get these until the last subset possible that is S(10) = 55.

Since, S(x) gives continuous integer values, we conclude that there are 56 distinct possible sums.

Intuition: the sums will be at least $0$ (empty set) and at most $1+2+3+\cdots + 10 = 55$ . It seems that any number between 0 and 55 can be also written as a sum of distinct elements of the set.

Claim: for the set $\{1,2,3,\ldots,n\}$ , the distinct sums that we can get is precisely the set $\{0,1,2,3,\ldots,\frac{1}{2}n(n+1)\}$ .

Base case ( $n = 1$ ): We can get both a sum of 0 (empty set) and a sum of 1 (from $\{1\}$ ).

Inductive step: assume our claim is true for $n$ . We will show the claim is also true for $n+1$ .

By induction, any element of $\{0,1,\ldots,\frac{1}{2}n(n+1)\}$ can be written as a sum of subsets of $\{1,\ldots,n\} \subset \{1,\ldots,n+1\}$ .

So we only need to show that the remaining set $A = \{\frac{1}{2}n(n+1)+1,\ldots, \frac{1}{2}(n+1)(n+2)\}$ can be written as sums of subsets of $\{1,\ldots,n+1\}$ . Letting $A'$ be the result of subtracting each element of $A$ by $n+1$ , we have that the largest element of $A'$ is

$\frac{1}{2}(n+1)(n+2) - (n+1) = [1+2+3+\cdots + (n+1)] - (n+1)$ $= 1+2+\cdots + n = \frac{1}{2}n(n+1)$

Since know from induction that any element of $A'$ can be written as a sum of elements from $\{1,\ldots,n\}$ , we may just add $n+1$ to each element of $A'$ to get the elements in $A$ .

Note: we use the formula for triangular numbers: $1+2+\cdots + n = \frac{1}{2}n(n+1)$

It is clear that the maximum sum is 55 and minimum 0. since we can construct sum up to 10 easily by taking one element as subset and clearly one can also calculate sum to 55 in similar way. For example:- 11 = 10 +1,till 19 = 10 + 9, now sum of three numbers, 20 = 10 + 9 + 1 and so on. Hence correct answer is 56 unique sum possible.

The lowest sum possible is 0 and the highest sum possible is 55 when all the elements have been taken (only once) .If we see carefully we find that all numbers from 0 to 55 can be constructed somehow from the set and so the different values of the sum can be 56 ...

Let us find the maximum sum we could obtain. This would be the sum of the largest subset, the whole set, the sum of the elements of which is equal to 1+2+3+...+10. By the formula for the sum of the first n natural numbers (S = n(n+1)/2), we get that this is indeed equal to 10*11/2 = 55. Therefore, we can obtain the sum 55, and to get a positive sum greater than 0 and not larger than 55 we simply need to take the appropriate integers out; which can be done as they all differ by one. Moreover, taking the null set (empty set) as a subset will give us the sum 0, thus resulting in a total of 55+1 = 56 possible sums.

Because the range of numbers is 1,2,3...10, considering subsets of between 1 to 10 numbers, we will have distinct sums from 1 to 1+2+3+4+5..+10 = 55. Then you include the sum of the empty subset = 0 Which gives a total of 56 distinct sums. 0 .. 55

The smallest possible sum is 0 ( empty subset) and the largest is 55, and using the fact that we van get every single sum from 0 to 55, we can have 56 different sums.

0->1 1->2 ... 55->56; min value 0 and max value is 55 from the given set. Each number between 0-55 can be represented by the given set.

maximum possible sum 55 and every sum in between is attainable.........so total 55=1=56

The máx value is 55 when you some all the values, the integeres is min 0 and máx 55 so total is 56

{} means 0

In the next subsets, almost all of them will have the same sum, for example :

• 25 can be the sum of {1,5,9,10}, {2,4,9,10}, {1,2,3,4,5,10}, etc
• 36 can be the sum of {2,3,4,5,6,8,9,}, etc

It can be used for all the other sum of the numbers because it says distinct sums from the subsets

Also, because the largest sum from {1,2,3,4,5,6,7,8,9,10} is 55, then the total distinct sum is from 0 to 55

Thus, the answer is $\boxed{56}$

If we consider the above set, we see that the greatest possible sum is $1+2+3+4+5+6+7+8+9+10=55$ , while the least possible sum is an empty subset, or 0 . Because each of the sums in between these two values can be created using the numbers from the set, the number of distinct sets is number of integers between 0 and 55, inclusively, which is $\boxed{56}$ .

Solution The sum of all the elements is $1+2+3+4+5+6...+10 = 55$ . Note that you can create subsets with sum of $0$ all the way to $55$ . Hence, the answer is simply $55+1$ (which is when sum is $0$ ) $= \boxed{56}$ .

Proof (by observation)

Observe the following pattern:

In set { $1,2$ }, the sums { $0, 1, 2, 1+2 = 3$ } can be form, which is literally all the sums from $0$ to $3$ .

In the set { $1,2,3$ }, similarly, the sums { $0,1,2,3,1+3 =4, 2+3 = 5, 1+2+3 = 6$ } can be form - these are also all the sums from $0$ to $6$ .

Generalising the pattern, in the set { $1,2, ..., (n-1), n$ }, the sums { $0,1,2,... (n-1), n, (n+1), (n+2), ... (n+ (n-1)), (n + (n-1) +1 = 2n), (n + (n-1) + 2)+ .... + (n+ (n-1) +(n+2)+...+2+1)$ } which are all the sums possible from $0$ to $(n+ (n-1) +(n+2)+...+2+1)$

This pattern will apply to the set { $1,2,...,9,10$ } as well. Hence, since $1+2+...+10 = 55$ , there are $55+1=56$ distinct sums.

The minimum possible is 0 (for the empty set). The maximum possible is 55 (for the set including them all). Convince yourself that we can achieve any number in between...