2
$\begingroup$

Let there be $B \subset \{10,11,...,99\}$, with $|B| =10$. I need to prove, using the pigeonhole principle, that there are at least two disjoint subsets of $B$ (and none empty) where the sums of their elements are identical. I.e. $\exists B_1 \ne \varnothing, B_2 \ne \varnothing$ such that $B_1 \bigcup B_2 = B$, $B_1 \bigcap B_2 =\varnothing$ and $$\sum_{a \in B_1} a = \sum_{b \in B_2} b$$

$\endgroup$
6
  • 1
    $\begingroup$ This looks related to math.stackexchange.com/questions/320555/… $\endgroup$ – Arnaud D. Jan 7 '17 at 15:41
  • $\begingroup$ What does "a set of the integers {10-99}" mean? Is $B=\{10,11,12,\ldots, 99\}$ or is $B$ an unspecified subset of $\{10,11,12,\ldots, 99\}$? In the first case, you can pick $\{10,99\}$ and $\{11,98\}$. In the second case, you have problems if $B=\{97,98,99\}$, for example. - You may want to check back with the original problem statement (I suspect that $B\subset\{1,2,3,\ldots,99\}$ and $|B|=10$) $\endgroup$ – Hagen von Eitzen Jan 7 '17 at 15:41
  • $\begingroup$ You're correct, I forgot to mention that B is a set of exactly 10 integers. Ive edited the original question. Arnaud, it seems similar but I have a requirment that subsets will be foreign where as in that question from what I understand two different groups may have two people the same age. $\endgroup$ – Ariel Jan 7 '17 at 15:49
  • $\begingroup$ I think you mean 'disjoint' when you say 'foreign': two sets $S$ and $T$ are disjoint if $S \cap T = \varnothing$. Please edit your question if this is the case. $\endgroup$ – TonyK Jan 7 '17 at 15:58
  • $\begingroup$ @TonyK Thanks. done. $\endgroup$ – Ariel Jan 7 '17 at 16:02
4
$\begingroup$

A $10$-element subset $B$ of $\{10,\ldots,99\}$ has a sum of at most $90+\cdots+99=945$. This means that there can be at most 946 possible values $(0,\ldots,945)$ for the sum of elements in a subset of $B$.

But $B$ has $2^{10}=1024$ subsets. So at least two subsets, say $S$ and $T$, must have the same sum.

Obviously neither of these can be the empty set, because then the other (non-empty) set must have a non-zero sum. And if $S$ and $T$ are not disjoint, just remove the common elements from each set: $S\setminus T$ and $T\setminus S$. They will still have the same sum, and they will still be non-empty.

This argument goes through unaltered if we allow $B$ to be a subset of $\{0,\ldots,106\}$.

$\endgroup$
6
  • $\begingroup$ finally got it. thanks! :) $\endgroup$ – Ariel Jan 7 '17 at 16:25
  • $\begingroup$ Can you please tell me when the sum will be zero... $\endgroup$ – Vidyanshu Mishra Jan 7 '17 at 16:40
  • $\begingroup$ @THELONEWOLF.: I am counting the empty set, which is why I say there are $1024$ subsets. (Later I explain why neither of $S$ and $T$ can in fact be empty.) $\endgroup$ – TonyK Jan 7 '17 at 17:00
  • $\begingroup$ But we have to choose sets with 10 elements then why empty set?? $\endgroup$ – Vidyanshu Mishra Jan 7 '17 at 17:01
  • $\begingroup$ @THELONEWOLF.: because we are looking at subsets of the $10$-element set $B$. Pay attention. $\endgroup$ – TonyK Jan 7 '17 at 17:02

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.