0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – user481779 Dec 31 '17 at 11:18
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user481779 Dec 31 '17 at 11:41
  • $\begingroup$ @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]$. $\endgroup$ – PJK Dec 31 '17 at 11:52
  • $\begingroup$ @RobertZ Sorry I got the question wrong . $\endgroup$ – user481779 Dec 31 '17 at 11:57
  • $\begingroup$ @PJK Yes, you are right. But the right end point is 945. Am I wrong? $\endgroup$ – Robert Z Dec 31 '17 at 12:01
  • $\begingroup$ @RobertZ One subset can contain only a maximum of $9$ elements for both those subsets to be nonempty. $\endgroup$ – PJK Dec 31 '17 at 12:04
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.