# Pigeonhole principle: From any ten two-digit numbers we can take two subsets with the same sum [duplicate]

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.

## marked as duplicate by lulu, Martin Sleziak, user223391, mrp, Namaste elementary-set-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Jan 15 '17 at 0:01

• There are $2^{10}-1$ non-empty subsets of $B$. If you can show that some two subsets must have the same sum, you can also infer that there are two disjoint subsets with the same sum. So leave it until the end. – Joffan Jan 14 '17 at 16:46
• Incidentally there is no such thing as a disjoint subset of $B$ - "disjoint" describes a relationship between two subsets, not a property of one, so it doesn't really make sense to ask how many there are. – Joffan Jan 14 '17 at 17:12
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$.