Question

let s be a set of 10 distinct integers chosen from 1 through 50. show that s contains at least two different (but not necessarily disjoint) subsets of 4 integers that add up to the same number. (for instance, if the ten numbers are {3, 8, 9, 18, 24, 34, 35, 41, 44, 50}, the subsets can be taken to be {8, 24, 34, 35} and {9, 18, 24, 50}. the numbers in both of these add up to 101.). hint: use the pigeon hole principle. what are the pigeons and what are the pigeon holes?

Answer 1

Using the Pigeonhole Principle, we can show that among the possible subsets of four integers from a set of 10 distinct integers chosen from 1 to 50, at least two subsets will have the same sum, since there are more subsets (210) than possible sums (185).

Step-by-step explanation:

To show that a set s of 10 distinct integers chosen from 1 through 50 contains at least two different subsets of 4 integers that add up to the same sum, we can use the Pigeonhole Principle.

The possible sums of four distinct numbers from the set {1, 2, ..., 50} range from 10 (1+2+3+4) to 194 (47+48+49+50). The total number of different sums is 194 - 10 + 1 = 185.

When selecting subsets of four integers from our set of 10 integers, there are a total of Choose(10, 4) = 210 possible subsets.

Here, our subsets are the 'pigeons' and the possible sums are the 'pigeonholes'.

Since there are 210 subsets and only 185 possible sums, the Pigeonhole Principle ensures that at least two subsets must have the same sum.

This demonstrates that no matter the selection of 10 numbers, we can always find two subsets of four integers within it that sum to the same number, verifying the provided statement.