From a set of ten elements, how many subsets of four elements are possible: Pigeons?
Note that .
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?
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
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
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.
(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.)