Show that distinct subsets of a specific-cardinality subset have equal sums

Question

For $S\subset\{1,2,…,117\}$ and $|S|=10$, let $A$ and $B$ be distinct subsets of $S$. $s_A$ is the sum of the elements in $A$ and $s_B$ is the sum of those in $B$. How can I prove that there must be at least one such pair for which $s_A=s_B$?

I see that the pigeonhole principle is going to come in handy here through some comparison between the least and greatest possible sums, but I'm rusty on the exact methods for this technique.

Answer 1

Suppose that $m$ is the smallest element of $S$. Let $t$ denote the sum of all elements of $S$. If $$t-m+1<2^{10}-1=1023\,,\text{ or equivalently }t-m\leq 1021\,,$$ then the claim follows, since there are $2^{10}-1$ nonempty subsets of $S$ whose element sums lie (inclusively) betweem $m$ and $t$. Now, prove that $t-m\leq 1021$ must hold.

Well, we have $$t-m\leq \sum\limits_{k=0}^8\,(117-k)=1017\leq 1021\,.$$ The statement is still true if we take $S\subseteq \{1,2,3,\ldots,118\}$ instead. This argument does not work any longer because $$\sum\limits_{k=0}^8\,(118-k)=1026>1021\,.$$
However, note that if $S$ has four consecutive elements, then we are done. In the case that $S$ has no four consecutive elements, we have $$t-m\leq 118+117+116+114+113+112+110+109+108=1017\leq 1021\,.$$ Therefore, the claim is still true. It is a bit more challenging to show that the statement is also true if we take $S\subseteq \{1,2,3,\ldots,119\}$. It would be interesting to find out the largest integer $k$ for which there exists $S\subseteq \{1,2,3,\ldots,k\}$ with $10$ elements such that no two nonempty subsets of $S$ have the same element sum.