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.

  • $\begingroup$ There are 117! subsets, and fewer than 117+116+115+114+113+112+111+110+109+108 possible sums. $\endgroup$ – user3482749 Nov 16 '18 at 11:52
  • $\begingroup$ 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? $\endgroup$ – lulu Nov 16 '18 at 11:52
  • $\begingroup$ 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. $\endgroup$ – Michal Adamaszek Nov 16 '18 at 12:07
  • $\begingroup$ Yes, that is indeed what I meant. I'll have to pose it as a separate problem. $\endgroup$ – 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.

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.

  • $\begingroup$ Yes, this is the obvious case. I misstated the problem initially, but the misstatement is so severe that it's not worth editing to fix, and I'll simply pose it as a separate problem. This answer is fine for the question as stated above. $\endgroup$ – notadoctor Nov 16 '18 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.