Set of two-digit positive integers

**alexmahone** · August 12th 2011, 09:20 AM

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.

**abhishekkgp** · August 12th 2011, 10:58 AM

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

Thread: Set of two-digit positive integers

LinkBack

Thread Tools

Display

Set of two-digit positive integers

Re: Set of two-digit positive integers

Similar Math Help Forum Discussions

How many 10 digit positive integers with at most 7 consecutive zeros?

Probability that a randomly chosen two digit positive integer is divisible by 3 or 5.

How many five digit integers (10,000-99,999) are divisible by 5?

How many six-digit positive integers are there, which is evenly divisible by 4 or 9?

given positive integers a and b such that a|b^2, b^2|a^3, a^3|b^4,...

Search Tags