Pigeonhole Problem with Subsets

Question

Let $S$ be an arbitrary subset of $\{1, 2, ..., 99\}$ with $|S|=10$. Prove that there are two different subsets $A$ and $B$ (don't have to be disjoint) of $S$ so that $$\text{the sum of all the elements in $A$} = \text{the sum of all the elements in $B$}$$

Ex. $S=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$, the sets $A = \{1, 2, 3, 4\}$ and $B = \{1,9\}$ satisfy the condition since $1 + 2 + 3 + 4 = 10 = 1 + 9$.

Edit: I know that the total subsets would be $2^{10} = 1024$. I originally thought that the largest sum value is $945$, but that wouldn't make sense because that implies that both A and B are the same set, which they can't be, so I don't know what number to compare it to.

Answer 1

However we choose our set the largest the sum of all of the numbers in the set can be is 945.

There are $2^{10} = 1024$ subsets of our set.

There are $1024$ pigeons and $945$ pigeon-holes. One pigeon-hole must contain more than one pigeon.

Answer 2

Let $S$ be a subset of $\{1, \ldots, 100\}$ of size $10$. There are $1023$ non-empty subsets of $S$. Thus there are two distinct subsets $A$ and $B$ of $S$ whose sum of elements leave the same remainder when divided by $1000$. Since neither of these numbers exceed $1000$, we see that these two numbers must be equal and we are done.