disjoint subsets

May 2010
4
1
Let S be a set of 6 random positive integers whose sum is not bigger than 60.
Show that in any such set S there exists two non-empty , disjoint subsets whose elements have the same sum.


I've tried to somehow use the pigeon hole principle but I'm STUCK.

I know there are 2^6 possible subsets...though the empty set and the set with all six elements should be thrown away....which leaves us with 62 subsets.

Can anyone help me or "nudge" me in the right direction ?
 
May 2010
4
1
actually it was simpler than I could imagine.
there are 62 possible subsets...and only 59 possible sums for these.
so clearly at least 2 subsets have the same sum.

if the subsets are disjoint...we are done.
if the subsets share one or more elements...then we remove the shared elements ..and voilá .. we have our disjoint subsets with equal sums.