# Subsets with equal sums

I have a problem to solve but I am in need of your help.

Subjects with equal sums:

Prove that for every set $A$ which consists of $10$ double digit natural numbers( numbers among $10, \ldots, 99$), there are always two different subsets of $A$ that its elements have the same sum.

Thank you very much

-
Hint: how many different values can the sum of the elements of a subset of $A$ take, and how many different subsets of $A$ are there? – mjqxxxx Jan 3 '12 at 15:59

Our set $A$ has $10$ elements, and therefore has $2^{10}=1024$ subsets.
The smallest conceivable subset sum is $0$ (the empty set) and the largest is $945$ ($90$ to $99$). So $A$ has no more than $946$ different subset sums. It follows by the Pigeonhole Principle that two of the subset sums of $A$ must be equal. Note that if $X$ and $Y$ are distinct subsets of $A$ with the same subset sum, then $X\setminus(X\cap Y)$ and $Y\setminus(X\cap Y)$ have the same subset sum. So in fact $A$ has two disjoint subsets with the same sum.
You are right, the number of possible subset sums is less than $946$. In my answer above, I wrote "no more than" because I didn't want to bother counting the exact number. The number $946$, though an overestimate, is safely under %1024$, so we can use Pigeonhole. – André Nicolas Sep 29 '13 at 20:00$A \subset \{10, \ \dots, \ 99\} ,\ \left|A\right| = 10\Omega = \{I \subset A\}\Theta = \{\sum_{i \in I} \ i, \ I \in \Omega\}f :\Omega \to \Theta, \ f(I) = \sum_{i \in I} \ i$If we prove that$f$is not injective we have the solution:$\left| \Omega \right| = 2 ^ {10} = 1024\left| \Theta \right| \leq 1 + \sum_{i = 90 }^{99} \ i = 946$So:$\left| \Omega \right| \gneq \left| \Theta \right|$therefore$f$in not injective: we can find$I, \ J \in \Omega, \ I \neq J , \ f(I) = f(J) \$