4 Dec 2011
There are so many techniques in Mathematics that I am not aware of. Here is another problem, which I didn't even know how to begin to solve.
Prove that every set of ten distinct numbers between 1 and 100 contains 2 disjoint nonempty subset with the same sum
The proof is rather simple though.
First of all, a set of 10 elements has 2^10-1 nonempty subsets.
Next, we find that the maximum possible sum is 100 + 99 + 98 + … + 91, which is less than 1000, but we have 1023 subsets.
The technique is called pigeon hole, btw.
Therefore, it is impossible that every subset has unique sum.