Subsets of subsets (puzzle)...?

This is a fairly old problem. It is an application of the pigeonhole principle. Consider all the possible subsets of {1,5,24,25,45,67,70,78,84,90}. There are 2^10=1024 of those (1023 non empty). But the number of possible sums that these subsets can have ranges from 1 to 489 (the sum of the numbers in the set). Hence at least two of the subsets must have the same sum. If those are distinct, we are done. If they are not distinct, throw out the common elements from both of them. They still have the same sum and are now distinct.

The same argument works whatever the initial subset of ten elements is. That's because the highest possible sum is 91+92+...+100 = 955, which is still less than 1023.

Let S be any given 10-element subset of {1,2,3,...,98,99,100}. Note that S itself has 2^10 - 1 = 1,023 non-empty subsets.

For each of these 1023 subsets, the sum of the elements must be an integer that is greater than or equal to 1 and less than or equal to 100 + 99 + 98 + ... + 91 < 1,000. Therefore, there are less than 1,000 possible distinct sums of elements in these 1,023 subsets.

Therefore, the pigeonhole principle implies that there exist distinct subsets A and B of S such that the elements of A have the same sum as the elements in B. Furthermore, at least one element of A and at least one element of B are not in the intersection of A and B, since 1) A and B are distinct sets, 2) all elements are positive numbers, and 3) the elements of A have the same sum as the elements in B.

Subtracting the sum of the elements common to A and B from each of the equal sums, we find that the set of elements in A but not B, and the set of elements in B but not A, are two disjoint non-empty subsets whose elements have the same sum.

Have a blessed, wonderful day!