4
$\begingroup$

I've already known that the desired answer is 512. But, how can I get this answer? Can anybody show me how to get this answer with only using permutation or combination?

I can only think that the answer is 512, because sums to 28 is equal with finding half of all the sums of these subsets, 55.

Because 1+2+....+10= 55, and total subsets is 1024. So 28 is half of all the subsets, so the number of subsets must be half of the total, so the total subsets is 512.

Is my thinking can be considered as right answer? Thanks

$\endgroup$
  • 2
    $\begingroup$ As long as you make that idea formal you are on the right track. More precisely if a subset $B$ of $A$ satisfy such property, then compliment of $B$ does not satisfy the property. $\endgroup$ – Jack Yoon Apr 23 '15 at 16:01
7
$\begingroup$

I'd say you're on a good track, but more should be said. As you noted the sum of all elements of $A$ is $55$.

You should argue (using the $55$ fact) that for any subset $B$ of $A$, exactly one of $B$ and $B^c$ (complement of $B$) have a sum greater than or equal to $28$.

Then pairing up subsets of $A$ by complements, we see that exactly half the subsets of $A$ will have a sum greater than or equal to $28$.

$\endgroup$
  • $\begingroup$ How can we pairing the subsets of A with its complement? Can you show me an example to do that? It sounds unfamiliar to me. Thanks $\endgroup$ – akusaja Apr 23 '15 at 16:10
  • 1
    $\begingroup$ Example: We form the complementary subset pair $\{1, 3, 5, 6, 7, 8\}$ and $\{2,4, 9, 10 \}$. In this case $1+3+5+6+7+8\ge 28$; while $2+4+9+10 < 28$. $\endgroup$ – paw88789 Apr 23 '15 at 16:14
2
$\begingroup$

The correctness of paw88789's approach can perhaps be more clearly seen if we try a smaller set; that way, you can sit down and actually enumerate all the different possibilities. That can make a world of difference in terms of internalizing the approach.

Suppose we ask how many subsets of $\{1, 2, 3, 4, 5\}$ add up to a number $\geq 8$. The crucial idea is that we partition the set into two parts; these two parts are called complements of each other. Obviously, the sum of the two parts must add up to $15$. Exactly one of those parts is therefore $\geq 8$. There must be at least one such part, because of the pigeonhole principle (specifically, two $7$'s are sufficient only to add up to $14$). And if one part has sum $\geq 8$, the other part—its complement—must have sum $\leq 15-8 = 7$.

For instance, if I divide the set into parts $\{1, 2, 4\}$ and $\{3, 5\}$, the first part adds up to $7$, and its complement adds up to $8$.

Once one makes that observation, the rest of the proof is straightforward. There are $2^5 = 32$ different subsets of this set (including itself and the empty set). For each one, either its sum, or its complement's sum (but not both), must be $\geq 8$. Since exactly half of the subsets have sum $\geq 8$, the number of such subsets is $32/2$, or $16$.

The proof of the case for $\{1, 2, 3, \ldots, 10\}$ is exactly analogous.

$\endgroup$
1
$\begingroup$

Not a detailed solution, just some thought which might help to prove it. There are 1024 subsets in total. And you can pair each subset $S$ with $T =A-S$. And Now you can see that sum($S$) = 55 - sum($T$). If sum$(S)$ is $\geq 28$ then sum$(T)$ is $\leq 27$. So there are as many subsets with sum $\geq 28$ as subsets with sum $\leq 27$ . So there are exactly $\frac {1024}{2}$ subsets with sum $\geq 28$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.