# Pigeon Hole Principle: Six positive integers whose maximum is at most $14$

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

• 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). – ajotatxe Sep 19 '16 at 22:36
• 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? – fleablood Sep 19 '16 at 23:35
• Ajotaxte. Min sum is min elements. Max sum is min elements + 10+11+12+13+14. Max minus min is 60 < 63. – fleablood Sep 19 '16 at 23:45

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