Given a set $B \subseteq \{10,11,12,\dots,99\}$ such that $\lvert B\rvert = 10$ show there are at least two disjoint non empty subsets of $B$ such that their sum is equal.
I want to use pigeonhole principle, but a little confused, How can I know how many disjoint subsets of $B$ exists? Am I in the right direction?
Thanks.
There are $2^{10}-1 = 1023$ non-empty subsets of $B$. We know that the maximum possible sum of $B$ is $945$, so no subset sums to more than this and also no subset sums to less than $10$, leaving less than $1023$ possible sums.
Thus by the pigeonhole principle there must be some subsets of any choice of $B$ which sum to the same value. To get disjoint subsets, choose any pair of distinct subsets that sum to the same total and from each remove the common elements, which reduces their totals by the same amount. This leaves two disjoint subsets of $B$ with the same sum, as required.
The elements of $B$ could actually be chosen from a larger set, $\{0..117\}$, with a little more work to describe the range of possible sum values for subsets of $B$.