# Show that distinct subsets of a set have equal sums using pigeonhole principle

For $$S\subset\{1,2,...,117\}$$ and $$|S|=10$$, I need to show that distinct such subsets have equal sums. That is, if $$s_A$$ is the sum of the elements in one 10-cardinality subset and $$s_B$$ is the sum of another, distinct 10-cardinality subset, 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.

• There are 117! subsets, and fewer than 117+116+115+114+113+112+111+110+109+108 possible sums. Nov 16, 2018 at 11:52
• I don't understand. The subsets $(\underline {1,4},5,6,7,8,9,10,11,12)$ and $(\underline {2,3},5,6,7,8,9,10,11,12)$ obviously have the same sum. Is that all you are asking?
– lulu
Nov 16, 2018 at 11:52
• I think what you really are asking is to prove that $S$ has two distinct subsets with the same sum. Otherwise @lulu has the answer. Nov 16, 2018 at 12:07
• Yes, that is indeed what I meant. I'll have to pose it as a separate problem. Nov 16, 2018 at 19:11

For a subset of cardinality $$10$$, the smallest sum is $$1+2+3+...+10 =55$$ and the largest is $$108+109+...+117 = 1125$$
Therefore we have only $$1125-54= 1071$$ possible sums.
The number of such subsets is $$\binom {117}{10} \approx 9\times 10^{13}$$ which is much higher the number of possible sums.