Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

2 Answers 2

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.

share|improve this answer
    
Actually, "A" has less than 946 different subset sums. Because one-digit numbers are not in the set. (subset sum can't be 1, 2, ... or 9) So there is 937 different subset sums. –  Mahdi Ghiasi Sep 29 '13 at 19:45
    
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) $

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.