Pigeonhole Principle

Printable View

April 19th 2009, 03:51 PM
datboitom

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.
April 19th 2009, 04:23 PM
NonCommAlg

Quote:

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.$
April 19th 2009, 04:30 PM
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?
April 19th 2009, 04:52 PM
NonCommAlg

Quote:

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.
April 19th 2009, 05:39 PM
datboitom

Alright, thanks for the help.