# Given a set $A \subseteq \{10,11,12,13…98,99\}$ such that $|A|=10$. Prove using Pigeonhole Principle there are 2 disjoint subsets with the same Sum.

Given a set $A \subseteq \{10,11,12,...98,99\}$ such that $|A|=10$. Prove using Pigeonhole Principle there are 2 disjoint non-empty subsets of $A$ with the same Sum.

Direction or Hint would be appreciated.

• Firstly you can calculate the number of ways of selecting 2 disjoint subsets with 2 elements each and then you can calculate the different number of sums possible if that comes out to be less than your first calculation then you are done – user481779 Dec 31 '17 at 11:18

Hint. The sum of the elements of a non-empty subset of $A$ is an integer in the interval $$\left[10,\sum_{k=90}^{99}k\right]=[10,945].$$ Moreover $A$ has $2^{10}-1=1023$ non-empty subsets.

• Set A has exactly ten elements but what I can comprehend from your solution is that you have calculated number of subsets of A which I don't think is relevant with the context of problem. Please correct me if I am wrong. – user481779 Dec 31 '17 at 11:41
• @RobertZ Shouldn't the range of integers be the sum of all the numbers in the possible nonempty subsets of $A$? i.e. $[10, 855]$. – PJK Dec 31 '17 at 11:52
• @RobertZ Sorry I got the question wrong . – user481779 Dec 31 '17 at 11:57
• @PJK Yes, you are right. But the right end point is 945. Am I wrong? – Robert Z Dec 31 '17 at 12:01
• @RobertZ One subset can contain only a maximum of $9$ elements for both those subsets to be nonempty. – PJK Dec 31 '17 at 12:04

The range of sums of a subset of $|A| \le 10$ is $\le 21 (10+11)$ and $945\ge (90+91+...+99)$, therefore $925$ different sums you can get from a subset of $\{10,11,...,98,99\}$ if $|A|\le10.$

In a set $A, |A| = 10$, there are $2^{|A|} - 1$ non-empty subsets = $1023$.

$1023 \gt 945$, therefore considering $945$ "pigeonholes", atleast $2$ disjoint sets will share the same sum. We can force our sets $A,B\, s.t \,\Sigma A = \Sigma B$ to be disjoint easily by -

$$A = A \backslash \{A\cap B\}$$ $$B = B \backslash \{B\cap A\}$$

As required.