# Discrete Math, Pigeon Hole Principle/Sum of Elements of Subsets

• Mar 25th 2009, 08:45 PM
therpgmaker
Discrete Math, Pigeon Hole Principle/Sum of Elements of Subsets
Ok, so the question is to show for any set A of positive integers taken from {1,2,...,12}, A must contain two disjoint subsets whose elements when added up give the same sum.

Now, reading around on this site, what I have so far is that there are 2^6 possible subsets of a 6-element set, and the maximum possible sum is 57. I believe I'm supposed to then use the pigeon hole principle to show that it is true, but I'm not sure how to calculate the amount of disjoint subsets that have the same sum, which I'm thinking I have to find. Can someone help me out please?
• Mar 26th 2009, 01:20 AM
Hello therpgmaker

Welcome to Math Help Forum!

Sorry, but I don't think this question makes sense, as you have stated it.
Quote:

for any set A of positive integers taken from {1,2,...,12}
There must be a minimum number of elements in A, otherwise it is clearly untrue that
Quote:

A must contain two disjoint subsets whose elements when added up give the same sum
For instance if A = {1}, the only subsets of A are \$\displaystyle \oslash\$ and A itself.

• Mar 26th 2009, 05:41 AM
therpgmaker
Oh, crap, I left out an important piece of information. It's for any set of six positive integers taken from 1 to 12.
• Mar 26th 2009, 09:35 AM
Pigeon-hole principle
Hello therpgmaker

You have nearly all the bits you need to solve this problem now. You've said that the maximum sum that can be made with 6 of the elements of {1, 2, ..., 12} is 57. So there at most 58 different sums (0 through 57) that can be made by adding the elements of a subset of A, where A is itself a subset of six elements from {1, 2, ..., 12}.

And, as you said, any set A that contains 6 elements has \$\displaystyle 2^6\$ = 64 distinct subsets. So by the pigeonhole principle, the elements of at least two of these subsets must have the same sum.

The only question that remains is: can we prove that A has two disjoint subsets with the same 'element-sum'? Yes. Since if P and Q are two subsets of A with the same element-sum, then the sets (P - Q) and (Q - P) will also have the same element sum, because the same elements (those common to both P and Q) have been removed. And, of course, (P - Q) and (Q - P) are disjoint.

That completes the proof.