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