The subset dilemma

Consider two disjoint subsets X and Y of A whose union is A. Then S(X) + S(Y) = 1 + 2 + ... + 10 = 55, where S(X) is the sum of all the elements of X. If S(X) < 28, then S(Y) > 27 or S(Y) >=28. Hence Y is one of the subsets we are looking for. On the other hand, if S(X) >= 28, then S(Y) < 28. Hence X is one of the subsets we are looking for. Hence for every pairing of disjoint subsets X and Y such that X U Y = A, exactly one of S(X) and S(Y) is greater than or equal to 28. Thus, since there are 2^10 subsets of A, there 2^9 = 512 subsets of A whose sum of its elements is greater than or equal to 28.

We would establish a bijective correspondence with the subsets $S$ of $N$ which have a sum of elements which is at least 28 and the subsets $T$ of $N$ which have a sum of elements which is lesser than 28. [Note: He used $S$ for both types of subsets. Using $T$ makes the proof unambiguous and easier to read. - Calvin]

For any subset $S$ of $N$ , we could pair it with the complement of $S$ , which we will denote as $T_S$ . This is also a subset of $N$ . Since the sum of the elements of $N$ is $1 + 2 + ... + 10 = 55$ , the sum of elements in $T_S$ is less than 28, because if $x < 28$ , then $55 - x > 28.$

Every distinct subset $S$ of $N$ that has a sum of elements less than 28 has a distinct complement $T_S$ , because the complement is all of the elements of $N$ after the elements in $S$ are removed, and if $S$ is different, the complement of $S$ would also be different.

This establishes a bijective correspondence with the subsets $S$ of $N$ and the subsets $T$ of $N$ . For each subset, we could choose whether or not to include each of the elements of 1, 2, ..., 10, so there are $2^{10} = 1024$ possible subsets. Since half of those subsets have a sum of elements which is at least 28, the number of subsets which has a sum that is at least 28 is $\frac {1024 }{2} = 512$ .

If S is a subset of A, then S' = A\S = {x|x in A and x not in S} is the complement of S. If the sum of the elements of S is k, then the sum of the elements of S' is 45-k. There is then a natural bijection between X = the subsets of A whose elements are greater than or equal to 23 and Y = the subsets of A whose elements are less than 23 by taking the function f:X->Y f(A) = A'. Furthermore, X and Y form a partition of A. Then the cardinality of X = the cardinality of Y = 1/2 the cardinality of A = 1/2 * 2^10 = 512.

The first step is to calculate how many subsets we are dealing with here in total. For a set with n distinct elements, the number of subsets is calculated from the binomial sum and comes out to {2}^{n}.

Thus, in our set A there are {2}^{10} = 1024 distinct subsets.

The next step is to see how the sum of elements of these subsets are distributed. A starting point is to place bounds on the sums. The smallest is of course 0, given by the empty set \left{ \right}. And the largest is given by the sum of elements of the set itself. This is:

1+2+3+4+5+6+7+8+9+10 = 55

So the sum of elements ranges from 0 to 55. The final step is to recognize that exactly half the subsets have elements whose sum is greater than or equal to 28. We can see this from the fact that the requirement 28\leq sum splits the interval [0, 55] exactly in half, and from the fact that sums are distributed symmetrically about the midpoint of the interval [0,55].

So the number of subsets meeting the given requirement is half the total number of subsets:

\frac{1024}{2} = 512, which is our answer.

Let $S$ be a subset of $A$ . Let $S'$ be the set of all elements in $A$ that are not in $A$ . If the sum of the elements of $S$ is $k$ , then the sum of the elements of $S'$ is $55 - k$ since $1+2+ \cdots +10=55$ . Therefore, there is a one-to-one correspondence between sets with sum $k$ s.t. $0 \leq k \leq27$ and sets with sum $k$ s.t. $28 \leq k \leq 55$ . It follows that the desired answer is the half of the total number of subsets of $A$ , or $\frac{2^{10}}{2} = 512$ .

The sum of all the elements of $A$ is $1+2+\ldots +10 = \frac {10 \times 11}{2} = 55$ . Let $B$ denote the set of subsets of $A$ whose sum of elements is greater than or equal to 28, and let $C$ denote the set of subset of $A$ whose sum of elements is less than or equal to 27. Since $B \cup C$ represent all the subsets of $A$ , thus $|B| + |C| = 2^{10}$ .

Now, given $S$ a subset of $A$ , consider its complement $S^c$ . Since the sum of elements in these 2 sets is 55, exactly one of these sets is in $B$ and exactly one of these sets is in $C$ . Hence, $|B|=|C|$ .

Thus, $|B|= 2^9 = 512$ .

The answer is equal to ${10 \choose 1}+{10 \choose 2}+{10 \choose 3}+{10 \choose 4}+{10 \choose 5}/2=512$ .