# pigeon-hole

• Dec 10th 2008, 01:44 PM
NidhiS
pigeon-hole
Let S be a set of ten integers chosen from 1 through 50. Show that the
set has at least two different (but not necessarily disjoint) subsets
of exactly four integers each that add up to the same number. (For
instance, if S = {3,8,9,18,24,34,35,41,44,50} then the subsets can be
taken to be {8,24,34,35} and {9,18,24,50}; these borth have sums of
101.Show this using the pigeonhole principle.

I'm clueless (Worried)
• Dec 10th 2008, 02:08 PM
Plato
From a set of ten elements, how many subsets of four elements are possible: Pigeons?
Note that $\displaystyle 1 + 2 + 3 + 4 = 8\,\& \,47 + 48 + 49 + 50 = 194$.
That means the minimum sum of four is 8, maximum is 194; these are the pigeon holes.
Put that together with the first question what do you see?
• Dec 10th 2008, 02:22 PM
NidhiS
k so,

for a set S of 10 integers, the number possible subsets of 4 elements = 10C4
=70
Do i also need to calculate the number of ways in which I can choose 10 elements between 1 to 50? and then m,ultiply it with 70?

so, the number of elements in the pigeon = 70 (n)

and the sum goes from 8 to 194.
thus,the number of holes= 194 - 8 + 1 = 187 (m)

n < m(Thinking)
• Dec 10th 2008, 02:46 PM
Plato
I don't mean to insult, but if you do not understand the basics here then there is no way to help you with these questions.
$\displaystyle \frac{{10!}}{{4!\left( {10 - 4} \right)!}} = \frac{{\left( {10} \right)\left( 9 \right)\left( 8 \right)\left( 7 \right)}}{{4!}} = 210$.
You need to know the basics here.
If you don’t, then there is no need to ask for help.
• Dec 10th 2008, 02:55 PM
NidhiS
oh well that was just a calculation mistake.I over looked something.Not to offend you either

1+2+3+4 = 10 and not 8 (basics)

Thanks,
• Dec 10th 2008, 05:00 PM
awkward
Quote:

Originally Posted by Plato
From a set of ten elements, how many subsets of four elements are possible: Pigeons?
Note that $\displaystyle 1 + 2 + 3 + 4 = 8\,\& \,47 + 48 + 49 + 50 = 194$.
That means the minimum sum of four is 8, maximum is 194; these are the pigeon holes.
Put that together with the first question what do you see?

The problem statement did not say the integers are distinct.

So the minimum sum is 1+1+1+1 and the maximum is 50+50+50+50.
• Dec 11th 2008, 03:11 AM
Plato
Quote:

Originally Posted by NidhiS
Let S be a set of ten integers chosen from 1 through 50. Show that the set has at least two different (but not necessarily disjoint) subsets of exactly four integers each that add up to the same number.

Quote:

Originally Posted by awkward
The problem statement did not say the integers are distinct. So the minimum sum is 1+1+1+1 and the maximum is 50+50+50+50.

I completely disagree with you on that.
How do you account for “subsets of exactly four integers each”?
I do not count the collection [1,1,1,1] as subset.
• Dec 11th 2008, 01:41 PM
awkward
Quote:

Originally Posted by Plato
I completely disagree with you on that.
How do you account for “subsets of exactly four integers each”?
I do not count the collection [1,1,1,1] as subset.

Yes, I guess you're right about that. Since the problem statement referred to a set of 10 integers and subsets of 4 integers, the implication is that set members are distinct. (Bow)

(The problem's conclusion still holds if the integers are not required to be distinct, however, but then to get the terminology correct the collections involved should be called multisets.)