Subsets of Subsets

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.

The end