Results 1 to 6 of 6

Math Help - subsets whose elements have equal sums (Pigeonhole)

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    27

    subsets whose elements have equal sums (Pigeonhole)

    So I'm not sure where to start with this. I did a search and found some similar threads, but I'm still stumped.

    Let A\subseteq\{1,2,3,...,25\} where \vert A\vert=9. For any subset B of A let s_B denote the sum of the elements in B. Prove that there are distinct subsets C,D of A such that \vert C\vert=\vert D\vert=5 and s_C=s_D.

    So I know there are \frac{25!}{16!} possible subsets A. And I also know that the maximum sum of any subset A is 205. But beyond that I don't really know what to do here.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by CropDuster View Post
    So I'm not sure where to start with this. I did a search and found some similar threads, but I'm still stumped.

    Let A\subseteq\{1,2,3,...,25\} where \vert A\vert=9. For any subset B of A let s_B denote the sum of the elements in B. Prove that there are distinct subsets C,D of A such that \vert C\vert=\vert D\vert=5 and s_C=s_D.

    So I know there are \frac{25!}{16!} possible subsets A. And I also know that the maximum sum of any subset A is 205. But beyond that I don't really know what to do here.
    Actually there are \binom{25}{9} possible subsets A and the maximum sum of elements of A is 189, but those aren't the numbers we're interested in.

    The minimum sum of elements of a subset of cardinality 5 here is 1+...+5 = 15. The maximum is 21+...+25 = 115. There are a total of 101 possible values for such a sum, then. There are \binom{9}{5}=126 possible 5-subsets of any given A with cardinality 9. Thus we apply the pidgeonhole principle noting that 126 > 101.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2010
    Posts
    27
    Quote Originally Posted by undefined View Post
    Actually there are \binom{25}{9} possible subsets A and the maximum sum of elements of A is 189, but those aren't the numbers we're interested in.

    The minimum sum of elements of a subset of cardinality 5 here is 1+...+5 = 15. The maximum is 21+...+25 = 115. There are a total of 101 possible values for such a sum, then. There are \binom{9}{5}=126 possible 5-subsets of any given A with cardinality 9. Thus we apply the pidgeonhole principle noting that 126 > 101.
    Thanks, for you're help!

    I see that you're right about my math being way off. And I understand you're reasoning, but I don't understand where you are getting "a total of 101 possible values for such a sum".
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by CropDuster View Post
    Thanks, for you're help!

    I see that you're right about my math being way off. And I understand you're reasoning, but I don't understand where you are getting "a total of 101 possible values for such a sum".
    Suppose set X = {15, 16, ... , 115}. You can see that |X| = 101.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jun 2010
    Posts
    27
    Ah! Yes, thank you so much! Been racking my brain over this one. For some reason I always try to make these discrete math problems harder than they are.

    Thanks again!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by CropDuster View Post
    Ah! Yes, thank you so much!
    You're welcome!

    Quote Originally Posted by CropDuster View Post
    For some reason I always try to make these discrete math problems harder than they are.
    I often do this as well!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Equal sums...?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 10th 2012, 10:45 AM
  2. Replies: 4
    Last Post: March 26th 2009, 04:10 PM
  3. Connected subsets of {(z,w) in C^2: z not equal to w}?
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 26th 2009, 12:05 PM
  4. Replies: 7
    Last Post: February 20th 2009, 03:05 PM
  5. Replies: 1
    Last Post: October 8th 2007, 06:13 PM

Search Tags


/mathhelpforum @mathhelpforum