subsets whose elements have equal sums (Pigeonhole)

**CropDuster** · August 6th 2010, 05:48 PM

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.

**undefined** · August 6th 2010, 06:25 PM

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.

**CropDuster** · August 7th 2010, 08:22 AM

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".

**undefined** · August 7th 2010, 08:30 AM

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.

**CropDuster** · August 7th 2010, 08:35 AM

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!

**undefined** · August 7th 2010, 08:38 AM

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!

Thread: subsets whose elements have equal sums (Pigeonhole)

LinkBack

Thread Tools

Display

subsets whose elements have equal sums (Pigeonhole)

Similar Math Help Forum Discussions

Equal sums...?

Discrete Math, Pigeon Hole Principle/Sum of Elements of Subsets

Connected subsets of {(z,w) in C^2: z not equal to w}?

[SOLVED] Proof for equal sum subsets (pigeonhole principle)

Need help with showing that orders of elements are equal...

Search Tags