Originally Posted by

**Skittles8768** Let S = set of 10 integers n, where each n satisfies the inequality, 1 ≤ n ≤ 50. Show that set S contains at least two different (not necessarily disjoint) subsets of four integers that add up to the same number.

i have the answer from the solutions manual, but why is the maximum possible sum of elements of any subset of S is 41+42+…+50 = 455 instead of 47+48+49+50? why isnt the "two different subsets of four integers" taken into account in the calculations?

the complete solution is:

Let T be the set of all possible sums of elements of subsets of S and define a function F from P(S) to T as follows: for each subset X of A let F(X) be the sum of the elements of X.

By Theorem 5.3.1, P(S) has 2^10= 1024 elements

The the maximum possible sum of elements of any subset of S is 41+42+…+50 = 455

The minimum possible sum of elements of any subset of S is 1+2+…+10 = 55

Hence T has 455 – 55 +1 = 401 elements

Because 1024 > 401, the pigeonhole principle guarantees that F is not one-to-one.

Thus there exists distinct subsets S_1 and S_2 such that F(S_1)= F(S_2)

This implies that the elements of S_1 add up to the same same as the elements of S_2