note that if we get two sets $A,B$ (not necessarily disjoint) with this property, then the same is also true for the sets $A\setminus (A\cap B),B\setminus(A\cap B)$. to get two distinct subsets with the same sum, note that there are $2^{10}-1$ different non-empty subsets. from amongst the integers $10,\ldots,99$ any subset of size atmost $10$ can have a maximum sum of atmost $91+92+\cdots+99=945$ and so necessarily the sums of various subsets from among all the subsets of the chosen set of $10$ elements can be atmost $945<1023$ and so the problem is solved.

I like your solution but I have a question, does the fact that there are 1023 subsets but at most the sum of one of these subsets is 945 mean that there are at least 78 subsets with equal sum? If not, then why?

TheLivingShadow wrote: I like your solution but I have a question, does the fact that there are 1023 subsets but at most the sum of one of these subsets is 945 mean that there are at least 78 subsets with equal sum? If not, then why? No it doesn't mean that , because $78$ set can have the same sum. @seshadri: You have a typo, not $ 91+92+\cdots+99=945 $ but $ 90+91+92+\cdots+99=945 $. Sorry everybody for bringing back an old topic.

wait...say we have the two disjoint subsets A and B each with sum k. So the sum of all the 10 elements is 2k, an even number. But the problem does allow us to pick the 10 numbers 10, 20, 30, ..., 80, 90, 91 for instance, with an odd sum. Am I missing something?

limac wrote: wait...say we have the two disjoint subsets A and B each with sum k. So the sum of all the 10 elements is 2k, an even number. But the problem does allow us to pick the 10 numbers 10, 20, 30, ..., 80, 90, 91 for instance, with an odd sum. Am I missing something? Yes nothing wrong! But the subsets may not have 5 elements each, so I do not see any problem.

yeah, but the sum has to be divided evenly between the two subsets, although we don't require both to have 5 elements each. So I just let that common sum be k for both of the subsets.

The subsets need not form a partition of the ten-element set. In your example, I might take {30} and {10, 20}, for example.

Oh ok, thank you very much.

Hi everybody! I have only a question: subset1 $\cup$ subset = $A$ ?

Better late than never Number of possible subsets = $2^{10} - 1 = 1023$ The subset with the maximum sum of elements is $\{90, 91 , \cdots , 99 \}$ (sum $= 945$) Subset with the minimum sum of elements is $\{10\}$ Let $S_1 , S_2 , \cdots S_{1023}$ be the sum of elements of all the possible subsets. There are 1023 'sums' but the number of 'possible sums' is less than $1023$ (because of the maximum bound) hence by PHP we can conclude there exist at-least 2 sums $S_i$ and $S_j$ ($i \neq j$) such that $S_i = S_j$. Recall that the original question asked us to prove that there exists disjoint subsets, now since we know that there exists at-least $2$ subsets with the same sum of elements, if they are not disjoint then remove the common element from the $2$ subsets, this strategy will keep the sum of elements of the $2$ subsets same but then they will be disjoint, and we are done.

OlympusHero wrote:

You have to prove that there are $945$ possible sums.

Wait am I missing something or is it clear that every sum before 945 can be made except for those less than $10+11+12+13+\ldots+19=145$ right?

Bumping. Please don't get mad at me because I bumped 24 minutes before 24 hours. The question is in the above post.

jasperE3 wrote: You have to prove that there are $945$ possible sums. You need to show that there are at most that many distinct sums. The main missing bit from OlympusHero's post was the note about disjointness from #2.

Okay, for anyone curious; I completely misread the problem - I'll fix it now. Thanks @jasperE3 and @oolite.

To begin, we find that the total number of subsets of a set with 10 elements, excluding the empty set and the entire set (since no other set can be disjoint to it) is $2^{10}-2=1022$. We now need to find the amount of possible sums of these subsets. The smallest sum occurs in the subset $\{10\}$, whose sum of 10. The largest sum occurs in the subset $\{91,92,...,98,99\}$, which has a sum of $$91+92+...+98+99=\frac{9*(91+99)}{2}=9*95= 855$$Since $855<1022$, there must be two subsets with the same sum by the Pigeonhole Principle. For sets with the same sum that are not disjoint, we can remove all elements that are common in both sets, preserving the fact that both sets have the same sum. Therefore, we have proved that in a set of 10 distinct two-digit numbers, it is always possible to find two disjoint subsets whose members have the same sum. $\square$

First notice that the total number of possible subsets is $2^{10}-2=1022$. Next, notice that the smallest possible sum is $10,$ and the largest possible sum is $$91+92+...+98+99=\frac{9\cdot(91+99)}{2}=9\cdot95= 855.$$So, by the Pigeonhole Principle, there must be $2,$ subsets that have the same sum. To make the set disjoint, we simply just remove the intersections of the $2$ sets and hence we are done. $\blacksquare$

The number of possible subsets is $\binom{10}{1}+\binom{10}{2}+\dots+\binom{10}{9}=1022.$ The possible sums range from $10$ to $91+92+\dots+99=855,$ so there are $846$ sums. Hence, by the Pigeonhole Principle, there must exist two distinct subsets $A$ and $B$ with the same sums. Notice that $A-A\cap B$ and $B-A\cap B$ satisfies the problem. $\square$

The number of total subsets is just $2^{10}-2=1022$. Now the maximum possible sum is $91+92+\ldots+99=855<1022$. Thus, at least two subsets must have the same sum. To make them disjoint, just remove their intersection.

First note that the disjoint condition is redundant. Indeed, if we can find two distinct subsets $A,B$ of the same sum, then certainly $A - B, B-A$ are of the same sum as well. Thus we are just trying to find two distinct subsets whose members have the same sum. There are $2^{10}-1=1023$ nonempty subsets total. However, the possible sums of any subset of a set of ten distinct two-digit numbers is lowerbounded by 10 and upperbounded by $90+91+\cdots+99=945$. Thus there are at most $945-10+1=846$ sums total, since $846<1023$ by the pigeonhole principle there must exist two subsets of the same sum.