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, 10: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, 11:58 AMabhishekkgpRe: Set of two-digit positive integers
there are possible proper subsets of . (A proper subset of is non empty subset of which is not equal to ). Let be a proper subset of .

Denote the sum of all the elements in by .

then for all proper subsets of .

So for any proper subset of there were admissible values of .

Now apply the Pigeon Hole Principle (a.k.a the dirchilet's box principle).

we had proper subsets and had only possible values of . So according to the Pigeon Hole Principle there are two proper subsets and of such that . If we are done. Else if then consider the proper subsets and that is delete the common elements from both and .