Subsets with equal sums

Question

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

Answer 1

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.

Answer 2

$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) $