0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ There are 117! subsets, and fewer than 117+116+115+114+113+112+111+110+109+108 possible sums. $\endgroup$ Nov 16, 2018 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, 2018 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$ Nov 16, 2018 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, 2018 at 19:11

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2018 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.