Results 1 to 5 of 5

Math Help - Pigeonhole Principle

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    7

    Pigeonhole Principle

    I have this question I need to complete but I'm not sure how to get started with it. Here is the question:

    Let S be a set of ten distinct integers between 1 and 50. Use the pigeonhole principle to show that there are two different 5-element subsets of S with the same sum.

    An example of that would be S= {1,2,3,4,5,30,31,32,33,34} and {30,2,3,4,5} and {31,1,3,4,5} have the same sum. And I need to prove this for any 10 elements.

    I don't really know how to get started with this. The only thing I have right now is that given a set of 10 elements there are: 252 distinct subsets of 5.

    And I think what I need to find out is the number of summations that do not yield the same result for a given subset of 5 elements, which would have to be under 252, which would then show some of them would have to be equal.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by datboitom View Post
    I have this question I need to complete but I'm not sure how to get started with it. Here is the question:

    Let S be a set of ten distinct integers between 1 and 50. Use the pigeonhole principle to show that there are two different 5-element subsets of S with the same sum.

    An example of that would be S= {1,2,3,4,5,30,31,32,33,34} and {30,2,3,4,5} and {31,1,3,4,5} have the same sum. And I need to prove this for any 10 elements.

    I don't really know how to get started with this. The only thing I have right now is that given a set of 10 elements there are: 252 distinct subsets of 5.

    And I think what I need to find out is the number of summations that do not yield the same result for a given subset of 5 elements, which would have to be under 252, which would then show some of them would have to be equal.
    Hint: the sum of any 5 distinct elements of \{1,2, \cdots , 50 \} is at most 46+47+48+49+50=240 < 252.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2009
    Posts
    7
    Tell me if this makes sense. So the max number of the sum is 240 and the minimum is 15. So then there is a total of 240-15 amount of different summations? Which is 225. 225 < 252 so some of them have to have the same sum? Is that correct or am I getting this concept wrong?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by datboitom View Post

    Tell me if this makes sense. So the max number of the sum is 240 and the minimum is 15. So then there is a total of 240-15 amount of different summations? Which is 225. 225 < 252 so some of them have to have the same sum? Is that correct or am I getting this concept wrong?
    it's almost correct! the different summations are actually at most 226 = 240 - 15 + 1 but we don't need it anyway. just the maximum 240 is good enough because 240 < 252.

    we're associating to any subset of 5 distinct elements a number, i.e. the sum of elements. we have 252 of these sets and at most 240 numbers available. now apply Pigeonhole Principle.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2009
    Posts
    7
    Alright, thanks for the help.
    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