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.

Printable View

- Aug 12th 2011, 09:20 AMalexmahoneSet 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.

- Aug 12th 2011, 10:58 AMabhishekkgpRe: Set of two-digit positive integers
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$.