# Thread: subsets whose elements have equal sums (Pigeonhole)

1. ## subsets whose elements have equal sums (Pigeonhole)

So I'm not sure where to start with this. I did a search and found some similar threads, but I'm still stumped.

Let $A\subseteq\{1,2,3,...,25\}$ where $\vert A\vert=9$. For any subset $B$ of $A$ let $s_B$ denote the sum of the elements in $B$. Prove that there are distinct subsets $C,D$ of $A$ such that $\vert C\vert=\vert D\vert=5$ and $s_C=s_D$.

So I know there are $\frac{25!}{16!}$ possible subsets $A$. And I also know that the maximum sum of any subset $A$ is 205. But beyond that I don't really know what to do here.

2. Originally Posted by CropDuster
So I'm not sure where to start with this. I did a search and found some similar threads, but I'm still stumped.

Let $A\subseteq\{1,2,3,...,25\}$ where $\vert A\vert=9$. For any subset $B$ of $A$ let $s_B$ denote the sum of the elements in $B$. Prove that there are distinct subsets $C,D$ of $A$ such that $\vert C\vert=\vert D\vert=5$ and $s_C=s_D$.

So I know there are $\frac{25!}{16!}$ possible subsets $A$. And I also know that the maximum sum of any subset $A$ is 205. But beyond that I don't really know what to do here.
Actually there are $\binom{25}{9}$ possible subsets A and the maximum sum of elements of A is 189, but those aren't the numbers we're interested in.

The minimum sum of elements of a subset of cardinality 5 here is 1+...+5 = 15. The maximum is 21+...+25 = 115. There are a total of 101 possible values for such a sum, then. There are $\binom{9}{5}=126$ possible 5-subsets of any given A with cardinality 9. Thus we apply the pidgeonhole principle noting that 126 > 101.

3. Originally Posted by undefined
Actually there are $\binom{25}{9}$ possible subsets A and the maximum sum of elements of A is 189, but those aren't the numbers we're interested in.

The minimum sum of elements of a subset of cardinality 5 here is 1+...+5 = 15. The maximum is 21+...+25 = 115. There are a total of 101 possible values for such a sum, then. There are $\binom{9}{5}=126$ possible 5-subsets of any given A with cardinality 9. Thus we apply the pidgeonhole principle noting that 126 > 101.
Thanks, for you're help!

I see that you're right about my math being way off. And I understand you're reasoning, but I don't understand where you are getting "a total of 101 possible values for such a sum".

4. Originally Posted by CropDuster
Thanks, for you're help!

I see that you're right about my math being way off. And I understand you're reasoning, but I don't understand where you are getting "a total of 101 possible values for such a sum".
Suppose set X = {15, 16, ... , 115}. You can see that |X| = 101.

5. Ah! Yes, thank you so much! Been racking my brain over this one. For some reason I always try to make these discrete math problems harder than they are.

Thanks again!

6. Originally Posted by CropDuster
Ah! Yes, thank you so much!
You're welcome!

Originally Posted by CropDuster
For some reason I always try to make these discrete math problems harder than they are.
I often do this as well!