Results 1 to 3 of 3

Math Help - Equal sums...?

  1. #1
    Super Member Rebesques's Avatar
    Joined
    Jul 2005
    From
    At my house.
    Posts
    542
    Thanks
    11

    Equal sums...?

    Given a subset A of the naturals that contains ten numbers chosen randomly from 10,11,..,99 prove that there exist two disjoint subsets of A, whose elements have equal sums.


    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Equal sums...?

    Quote Originally Posted by Rebesques View Post
    Given a subset A of the naturals that contains ten numbers chosen randomly from 10,11,..,99 prove that there exist two disjoint subsets of A, whose elements have equal sums.


    The number of proper subsets of A is 2^10-2=1022.

    The lowest value of the sum of elements of a proper subset is 10.

    The highest value of the sum of elements of a proper subset is 99+98+97+96+95+94+93+92+91+90=945.

    So, the number of different values for the sum of elements of a proper subset is 945-10+1=936.

    Then by the Pigeon-hole Principle two proper subsets have the same value for the sum of elements. If these subsets are disjoint, we are done. If, however, these subsets have some common element(s), we may consider the subsets formed by deleting the common element(s), and they will satisfy the required conditions.
    Last edited by alexmahone; January 10th 2012 at 11:11 AM. Reason: Rebesques spotted an error.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Rebesques's Avatar
    Joined
    Jul 2005
    From
    At my house.
    Posts
    542
    Thanks
    11

    Re: Equal sums...?

    Nice answer,
    thanks!






    pointless ps. the max sum equals 90+...99. Nothing changes
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. subsets whose elements have equal sums (Pigeonhole)
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: August 7th 2010, 09:38 AM
  2. Equal Sums of Like Powers
    Posted in the Math Forum
    Replies: 5
    Last Post: May 29th 2010, 03:55 AM
  3. Replies: 6
    Last Post: November 8th 2009, 04:28 AM
  4. Replies: 2
    Last Post: March 23rd 2009, 08:11 AM
  5. Showing two infinite sums are equal?
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: March 16th 2009, 12:13 PM

Search Tags


/mathhelpforum @mathhelpforum