# Any $B \subset \{10,11,…,99\}$, with $|B| =10$ has two subsets such that $\sum_{a \in B_1} a = \sum_{b \in B_2} b$

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$$

• This looks related to math.stackexchange.com/questions/320555/… – Arnaud D. Jan 7 '17 at 15:41
• 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$) – Hagen von Eitzen Jan 7 '17 at 15:41
• 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. – Ariel Jan 7 '17 at 15:49
• 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. – TonyK Jan 7 '17 at 15:58
• @TonyK Thanks. done. – Ariel Jan 7 '17 at 16:02

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\}$.

• finally got it. thanks! :) – Ariel Jan 7 '17 at 16:25
• Can you please tell me when the sum will be zero... – Vidyanshu Mishra Jan 7 '17 at 16:40
• @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.) – TonyK Jan 7 '17 at 17:00
• But we have to choose sets with 10 elements then why empty set?? – Vidyanshu Mishra Jan 7 '17 at 17:01
• @THELONEWOLF.: because we are looking at subsets of the $10$-element set $B$. Pay attention. – TonyK Jan 7 '17 at 17:02