0
$\begingroup$

I was reading this example from my textbook:

Let $S$ be a set of six positive integers whose maximum is at most $14$. Show that the sums of the elements in all the nonempty subsets of $S$ cannot all be distinct. For each nonempty subset $A$ of $S$ the sum of the elements in A denoted $S$ satisfies: $1 \leq S \leq 9 + 10 + 11 + 12 + 13 + 14 = 69 $

And then there are $2^6 - 1 = 63$ non empty subsets of $S$.

Could somebody please explain me the logic of $63$. How is this being calculated.

Thanks,

Rahul

$\endgroup$
  • $\begingroup$ Just for curiosity: since there are more possible results than subsets, how does the textbook finish the problem? (If it is long, don't bother). $\endgroup$ – ajotatxe Sep 19 '16 at 22:36
  • $\begingroup$ The book is assuming you know that a finite set with n elements will have $2^n $ subsets including the empty set and the entire set itself. Do you know why? $\endgroup$ – fleablood Sep 19 '16 at 23:35
  • $\begingroup$ Ajotaxte. Min sum is min elements. Max sum is min elements + 10+11+12+13+14. Max minus min is 60 < 63. $\endgroup$ – fleablood Sep 19 '16 at 23:45
1
$\begingroup$

Imagine the six integers as either being in the subset or not in the subset. Each integer can have 2 states. For a total of $2^6=64$ total states or subsets. Subtracting out the empty set, you are left with 63 subsets.

$\endgroup$
0
$\begingroup$

We denote the size, or cardinality, of $S$ by $|S|=6$. Now for any nonempty set $X$ there are $2^{|X|}$ subsets of $X$ in total, these include $X$ itself and the empty set $\varnothing$.

So for your set there are $2^{|S|}=2^6$ subsets of $S$ in total. Since the empty set $\varnothing$ is empty by definition you must subtract $1$ from $2^6$ to obtain the number of nonempty sets.

$\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.