Results 1 to 2 of 2

Thread: Set of two-digit positive integers

  1. #1
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,114
    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 $\displaystyle 2^{10}-2=1022$ possible proper subsets of $\displaystyle H$. (A proper subset of $\displaystyle H$ is non empty subset of $\displaystyle H$ which is not equal to $\displaystyle H$). Let $\displaystyle K$ be a proper subset of $\displaystyle H$.
    Denote the sum of all the elements in $\displaystyle K$ by $\displaystyle \sigma_K$.

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

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

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: Jan 27th 2011, 07:03 PM
  2. Replies: 2
    Last Post: Jun 1st 2010, 02:49 AM
  3. Replies: 3
    Last Post: Jun 1st 2010, 01:41 AM
  4. Replies: 3
    Last Post: Feb 3rd 2010, 09:30 AM
  5. Replies: 4
    Last Post: Jan 30th 2010, 03:59 AM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum