Thread: Set of two-digit positive integers

1. 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.

2. Re: Set of two-digit positive integers

Originally Posted by alexmahone
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$.

let H be a ten element set of two-digit

Click on a term to search for related topics.