Prove that any set of $10$ positive integers less than or equal to $100$ will always contain two subsets with the same sum.
Can anyone help me with this problem? Thanks.
Let $S$ be a set consisting of ten distinct positive integers, each of them less than or equal to $100$.
How many subsets does $S$ have?
How big can the sum of the elements of $T$ possibly get, for any subset $T\subseteq S$?
By showing that $S$ has more subsets than possible sums-of-subsets, the pigeonhole principle then tells you that there are two distinct subsets whose sums are equal.