# Math Help - Pigeonhole Principle

1. ## Pigeonhole Principle

I have this question I need to complete but I'm not sure how to get started with it. Here is the question:

Let S be a set of ten distinct integers between 1 and 50. Use the pigeonhole principle to show that there are two different 5-element subsets of S with the same sum.

An example of that would be S= {1,2,3,4,5,30,31,32,33,34} and {30,2,3,4,5} and {31,1,3,4,5} have the same sum. And I need to prove this for any 10 elements.

I don't really know how to get started with this. The only thing I have right now is that given a set of 10 elements there are: 252 distinct subsets of 5.

And I think what I need to find out is the number of summations that do not yield the same result for a given subset of 5 elements, which would have to be under 252, which would then show some of them would have to be equal.

2. Originally Posted by datboitom
I have this question I need to complete but I'm not sure how to get started with it. Here is the question:

Let S be a set of ten distinct integers between 1 and 50. Use the pigeonhole principle to show that there are two different 5-element subsets of S with the same sum.

An example of that would be S= {1,2,3,4,5,30,31,32,33,34} and {30,2,3,4,5} and {31,1,3,4,5} have the same sum. And I need to prove this for any 10 elements.

I don't really know how to get started with this. The only thing I have right now is that given a set of 10 elements there are: 252 distinct subsets of 5.

And I think what I need to find out is the number of summations that do not yield the same result for a given subset of 5 elements, which would have to be under 252, which would then show some of them would have to be equal.
Hint: the sum of any 5 distinct elements of $\{1,2, \cdots , 50 \}$ is at most $46+47+48+49+50=240 < 252.$

3. Tell me if this makes sense. So the max number of the sum is 240 and the minimum is 15. So then there is a total of 240-15 amount of different summations? Which is 225. 225 < 252 so some of them have to have the same sum? Is that correct or am I getting this concept wrong?

4. Originally Posted by datboitom

Tell me if this makes sense. So the max number of the sum is 240 and the minimum is 15. So then there is a total of 240-15 amount of different summations? Which is 225. 225 < 252 so some of them have to have the same sum? Is that correct or am I getting this concept wrong?
it's almost correct! the different summations are actually at most 226 = 240 - 15 + 1 but we don't need it anyway. just the maximum 240 is good enough because 240 < 252.

we're associating to any subset of 5 distinct elements a number, i.e. the sum of elements. we have 252 of these sets and at most 240 numbers available. now apply Pigeonhole Principle.

5. Alright, thanks for the help.