Results 1 to 4 of 4

Math Help - pigeonhole principle

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    3

    pigeonhole principle

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Skittles8768 View Post
    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."
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    3
    yeah im pretty sure the author messed up, so would P(S) still have 2^10 elements?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    How many subsets of size four does a set of ten elements have?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help me with pigeonhole principle #2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 31st 2009, 11:23 PM
  2. help me with pigeonhole principle #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 31st 2009, 03:58 PM
  3. Pigeonhole principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 31st 2009, 03:59 PM
  4. Pigeonhole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 30th 2007, 03:15 PM
  5. Pigeonhole Principle
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: January 23rd 2006, 06:09 PM

Search Tags


/mathhelpforum @mathhelpforum