Question

Let A be a subset of {1, 2, . . . , 25} with |A| = 9. For any subset B of A, denote by SB, the sum of the elements in B. Prove that, no matter which elements A consists of, we can always find distinct subsets C and D of A such that |C| = |D| = 5 and SC = SD. (Hint: How many 5-element subsets of A are there? What is the largest 5-element sum?)

Answer 1

Answer:

Step-by-step explanation:

To solve this problem, we are going to apply the pigeon hole principle, which is as follows:

If m pigeons occupy n pigeon holes and m>n, then there must be at least one pigeonhole that holds more than one pigeon.

To apply this principle, we'll work the problem out to have a pigeon-pigenhole set up.

Consider the set $\{1,\dots, 25\}$. We want to define the posible values of SB for any B that is a subset of A. The lowest value of Sb would be considering B = $\{1,2,3,4,5\}$. In this case, the sum is 15. The highest value of SB would be when we consider the set B = $\{21,22,23,24,25\}$. In this case SB = 115. So now, consider A as stated and B any subset of A that has 5 elements. Since A has 9 elements and B has 5, we have $\binom{9}{5} = \frac{9!}{4!5!}=126$ different sets of 5 elements. Also, we have that

$15\leq S_b \leq 115$.

Note that given a B, SB is necessarily an integer between 15 and 115, and that given a B, we can assign its sum SB directly by summing up. Consider the different values of SB as pigeonholes and each 5-elements set as pigeons. We have in total 101 possible values (115-15 +1 = 101). Since each set B has a SB, then we are in the case in which we have more pigeons than pigeonholes, so it must happen that there is at least one pigeon hole (value of SB) that has more than one pigeon.