# 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. – user3482749 Nov 16 '18 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 '18 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. – Michal Adamaszek Nov 16 '18 at 12:07
• Yes, that is indeed what I meant. I'll have to pose it as a separate problem. – notadoctor Nov 16 '18 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.