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

Give it a kudos