pigeonhole principle

Nov 2009
3
0
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
 

awkward

MHF Hall of Honor
Mar 2008
934
409
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
Hi Skittles,

As I read the solution, it appears to be for a different problem, without the restriction that the subsets contain 4 elements each.

I.e., "Show that set S contains at least two different (not necessarily disjoint) subsets that add up to the same number."
 
Nov 2009
3
0
yeah im pretty sure the author messed up, so would P(S) still have 2^10 elements?
 

awkward

MHF Hall of Honor
Mar 2008
934
409
How many subsets of size four does a set of ten elements have?