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.
Best Answer
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.
Thus we have many distinct sets with the same sums.
We can put more restrictions on subsets to make the problem challenging. For example asking sums and square sums being the same.