Results 1 to 2 of 2

Math Help - Set of two-digit positive integers

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

    Set of two-digit positive integers

    Let H be a ten-element set of two-digit positive integers. Prove that H has two disjoint subsets A and B so that the sum of the elements of A is equal to the sum of elements of B.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

    Re: Set of two-digit positive integers

    Quote Originally Posted by alexmahone View Post
    Let H be a ten-element set of two-digit positive integers. Prove that H has two disjoint subsets A and B so that the sum of the elements of A is equal to the sum of elements of B.
    there are 2^{10}-2=1022 possible proper subsets of H. (A proper subset of H is non empty subset of H which is not equal to H). Let K be a proper subset of H.
    Denote the sum of all the elements in K by \sigma_K.

    then 10 \leq \sigma_K \leq 99+98+ \ldots + 91 = 855 for all proper subsets K of H.

    So for any proper subset K of H there were 855-10+1=846 admissible values of \sigma_K.
    Now apply the Pigeon Hole Principle (a.k.a the dirchilet's box principle).
    we had 1022 proper subsets and had only 846 possible values of \sigma. So according to the Pigeon Hole Principle there are two proper subsets K_1 and K_2 of H such that \sigma_{K_1}=\sigma_{K_2}. If K_1 \cap K_2 = \phi we are done. Else if K_1 \cap K_2 = L \neq \phi then consider the proper subsets K_1-K_1 \cap K_2 and K_2 - K_1 \cap K_2 that is delete the common elements from both K_1 and K_2.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: January 27th 2011, 08:03 PM
  2. Replies: 2
    Last Post: June 1st 2010, 03:49 AM
  3. Replies: 3
    Last Post: June 1st 2010, 02:41 AM
  4. Replies: 3
    Last Post: February 3rd 2010, 10:30 AM
  5. Replies: 4
    Last Post: January 30th 2010, 04:59 AM

Search Tags


/mathhelpforum @mathhelpforum